[数据结构与算法]114. 二叉树展开为链表

题目

递归

先对二叉树做一个先序遍历进行观察，发现题目实际上就是在先序遍历的基础上进行改进，使得左子树全都转移到右子树上去，因此写一个递归即可。

值得注意的是：需要把右子树放在左子树的最小右子树上，因此还需要有一个结点 p 来查找最小右子树。时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ .

class Solution {
public:
    void transform(TreeNode *root) {
        if(root == nullptr)
            return;
        transform(root->left);
        transform(root->right);
        if(root->left)
            if(root->right) {
                root->left->left = nullptr;
                TreeNode *p = root->left;
                while(p->right)
                    p = p->right;
                p->right = root->right;
                root->right = root->left;
                root->left = nullptr;
            }
            else {
                root->right = root->left;
                root->left = nullptr;
            }
    }

    void flatten(TreeNode* root) {
        transform(root);
    }
};

非递归

一开始考虑递归，因为它能够从子树开始操作，不容易出错。仔细分析一下发现，直接从头开始遍历右子树即可，原理都是一样的，遍历到最后一棵右子树即可。

class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode *t = root;
        while(t) {
            if(t->left)
                if(t->right) {
                    TreeNode *p = t->left;
                    while(p->right)
                        p = p->right;
                    p->right = t->right;
                    t->right = t->left;
                    t->left = nullptr;
                }
                else {
                    t->right = t->left;
                    t->left = nullptr;
                }
            t = t->right;
        }
    }
};