Leetcode.114二叉树展开为链表详细解析(c++递归)_二叉树展开为链表(c语言)的详细解题思路

Leetcode.114二叉树展开为链表详细解析(c++递归)

执行时间击败100%

主要思路：
第一步：将父节点的右子树，放在左子树的最右边的叶节点（也就是节点4）上，这样就由图中第一颗树转变到第二棵树
第二步：将第二棵树的左子树放在右子树的位置上，这样就由第二棵树转变为第三棵树
第三步：以父节点的右儿子（也就是第三棵树的节点2）作为父节点继续执行以上步骤一、二

注意事项：
1.执行第一步之前需要确定父节点的左儿子不为空

代码如下:

class Solution {
public:
    void flatten(TreeNode* root) {
        if(!root ) return ;
        while(!root->left ) //寻找左儿子不为空的父节点
        {
            root = root->right;
            if(!root) return ;
        }
        TreeNode* left = root->left;//左儿子
        TreeNode* now = left;//用于代替左儿子去寻找左节点的最右节点，因为左儿子后面还需要用到
        TreeNode* righttail ;//左子树的最右边的叶节点

        while(now->right) //找到左子树的最右边的叶节点
        {
            righttail = now->right;
            now = righttail;
        }
        righttail->right = root->right;//将父节点的右子树挂在其右子树的位置
        root->right = left;
        root->left = nullptr;//不要忘记left为空
        flatten(root->right);//有请下一位
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

如有错误及优化，欢迎在评论区指出