70-二叉树展开为链表

自己的做法

算法思想

使用递归。

递归函数：flattenTree。

函数功能：将给定树按先序遍历展开为单链表

函数参数：根节点root

函数返回值：展开为单链表的头节点

递归终止条件：传入的树根节点为空

具体实现：

首先要将root的左子树展开为单链表，root的右指针指向展开后的链表头节点。

因此首先保存root的右子树的根节点right_tree。

然后递归调用flattenTree，参数为root->left，root的右指针指向返回值。

然后从root遍历该链表，找到该链表的最后一个节点用来连接右子树展开后的单链表头节点。

最后展开右子树，连接起来即可。

算法实现

class Solution {
public:
    void flatten(TreeNode* root) {
        flattenTree(root);
    }

    TreeNode * flattenTree(TreeNode * root) {
        if(root == nullptr) {
            return nullptr;
        }
        TreeNode * right_tree = root->right;
        root->right = flattenTree(root->left);
        root->left = nullptr;
        TreeNode * left_head = root;
        while (left_head->right != nullptr) {
            left_head = left_head->right;
        }
        left_head->right = flattenTree(right_tree);
        return root;
    }
};

性能分析

设节点数为n。

时间复杂度：$O(n^2)$。共调用递归函数n次。遍历节点最好情况是每个节点都只有右子树，共遍历n次，最坏情况为每个节点都只有左子树，共遍历$\frac{n*(n - 1)}{2}$次。

空间复杂度：$O(n)$。最坏情况二叉树只有左子树或右子树，那么深度是n。

参考做法

算法思想

寻找前驱结点。

按先序遍历的顺序，对于以root为根的树来说，root左子树的最右节点的下一个节点就是root的右子节点。

所以可以找到root的左子树的最右节点right_node，也就是先序遍历root左子树的序列的最后一个节点。

然后让该节点的右指针指向root的左子树的根节点，然后root的右指针指向root的左子树的根节点，最后root左指针置为空。

这样就完成了左子树与右子树的连接。使用cur指向当前要处理的树的根节点，依次遍历cur的右指针，直到cur为空。

算法实现

class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode * cur = root;
        while (cur != nullptr) {
            if(cur->left != nullptr) {
                TreeNode * right_node = cur->left;
                while (right_node->right != nullptr) {
                    right_node = right_node->right;
                }
                right_node->right = cur->right;
                cur->right = cur->left;
                cur->left = nullptr;
            }
            cur = cur->right;
        }
    }
    
}    

性能分析

时间复杂度：$O(n)$。展开为单链表时，每个节点访问了一次。寻找前驱结点时，每个节点最多被访问一次。

空间复杂度：$O(1)$。