力扣114. 二叉树展开为链表（C++，解释一下别人的思路）

力扣114. 二叉树展开为链表（C++，解释一下别人的思路）

题目链接： 

114. 二叉树展开为链表 - 力扣（LeetCode） (leetcode-cn.com)https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/

 

思路：

我是先看的其他人的题解，所以就用他们的题解了。

拿到一个二叉树的题还是考虑“ *** 作+遍历”的思路。通过看图可以发现， *** 作就是把右子树转到左子树上，然后循环这个过程直到回到了根节点那里为止。那么这个 *** 作只需要几个额外的TreeNode*就能解决，类似于不同链表之间的遍历和插入，所以不需要新加一个 *** 作函数，在本函数内部就能解决。因为要找到右子树对右子树进行 *** 作，所以应该是后序遍历， *** 作放在后序遍历之后。

那么假设现在已经到了右子树了，该如何进行 *** 作呢？根据题意， *** 作完后原来root的左子节点是空，而右子节点指向的是左子节点的位置，所以先进行一个嫁接 *** 作，这一步是让右节点指向原来左边的那一串树；之后就需要把右边的分支补到左边的末尾上了，这就相当于一个链表寻尾再尾插的 *** 作了。

如果不太明白，可以用一个最简单的两层二叉树去模拟一下 *** 作的过程，这个明白之后，其余的大支都是这么做的，就能理解了。

class Solution {
public:
    void flatten(TreeNode* root)
    {
        if(!root)
        {
            return;
        }
        flatten(root->left);
        flatten(root->right);

        TreeNode* l=root->left;
        TreeNode* r=root->right;

        root->left=NULL;
        root->right=l;

        TreeNode* p=root;
        while(p->right)
        {
            p=p->right;
        }
      //  p=p->right;
        p->right=r;
    }
};