526互联

LeetCode 114. 二叉树展开为链表

发布时间 2023-05-27 10:34:16作者: 穿过雾的阴霾

思路1

class Solution {
public:
    void flatten(TreeNode* root) {
        while(root)
        {
            auto p=root->left;
            if(p)//找到左儿子的右链
            {
                while(p->right) p=p->right;
                //将右链插入
                p->right=root->right;
                root->right=root->left;
                root->left=NULL;
            }
            //此时root已经没有左孩子，往右孩子遍历
            root=root->right;
        }
    }
};

思路2

class Solution {
public:
    TreeNode* pre=NULL;//记录遍历顺序的前继节点
    void flatten(TreeNode* root) {//
        if(!root)   return;
        if(pre)
        {
            pre->right=root;
            pre->left=NULL;
        }
        pre=root;
        auto r=root->right,l=root->left;
        flatten(l);
        flatten(r);
    }
};