Flatten Binary Tree to Linked List

114. 二叉树展开为链表

分析

遍历二叉树的每个节点
如果当前节点存在左子树：
- 将左子树的最右节点找到，并连接到当前节点的右子树上
- 然后将当前节点的右子树替换为它的左子树，同时将左子树置为 null
移动到当前节点的右子节点，继续上述操作，直至遍历完所有节点

时间复杂度

时间复杂度 O(n)，每个节点遍历一次，且寻找左子树最右节点的过程也是线性的

空间复杂度

空间复杂度 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class Solution
{
public:
    void flatten(TreeNode* root)
    {
        while (root) // 遍历每个节点
        {
            TreeNode* p = root->left; // 获取当前节点的左子树
            if (p) // 如果存在左子树
            {
                // 找到左子树的最右节点
                while (p->right)
                    p = p->right;

                // 将左子树的最右节点与右子树连接
                p->right = root->right;

                // 将当前节点的右子树替换为左子树
                root->right = root->left;

                // 将左子树置为 null
                root->left = nullptr;
            }
            // 移动到右子节点
            root = root->right;
        }
    }
};