二叉树展开为链表 | 秋招知识库

方法一：头插法

采用头插法构建链表，也就是从节点 $6$ 开始，在 $6$ 的前面插入 $5$ ，在 $5$ 的前面插入 $4$ ，依此类推。

为此，要按照 $6 \to 5 \to 4 \to 3 \to 2 \to 1$ 的顺序访问节点。如何遍历二叉树，才能实现这个顺序？

既然 $1 \to 2 \to 3 \to 4 \to 5 \to 6$ 是先序遍历，那么 $6 \to 5 \to 4 \to 3 \to 2 \to 1$ 就是先序遍历的逆序，即按照右 - 左 - 根的顺序遍历二叉树。

遍历的同时执行头插法，把当前节点插在链表头节点 $head$ 的前面，然后更新 $head$ 为当前节点。一开始 $head$ 是空节点。

Python 解法1C++ 解法1

python

class Solution:
    head = None

    def flatten(self, root: Optional[TreeNode]) -> None:
        if root is None:
            return
        # 右 - 左 - 根
        self.flatten(root.right)
        self.flatten(root.left)
        root.left = None
        root.right = self.head  # 在头节点 head 的前面插入 root
        self.head = root  # 现在头节点是 root

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
    TreeNode* head = nullptr;

public:
    void flatten(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        // 右 - 左 - 根
        flatten(root->right);
        flatten(root->left);
        root->left = nullptr;
        root->right = head; // 在头节点 head 的前面插入 root
        head = root; // 现在头节点是 root
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 是二叉树的节点个数。
空间复杂度： $O (n)$ 。递归需要 $O (n)$ 的栈空间。

方法二：分治

方法一需要用到一个在 DFS 之外的变量 $head$ ，能否只在 DFS 中解决呢？

考虑分治，假如我们计算出了 $root = 1$ 左子树的链表 $2 \to 3 \to 4$ ，以及右子树的链表 $5 \to 6$ ，那么接下来只需要穿针引线，把节点 $1$ 和两条链表连起来：

先把 $2 \to 3 \to 4$ 和 $5 \to 6$ 连起来，也就是左子树链表尾节点 $4$ 的 $right$ 更新为节点 $5$ （即 $root . right$ ），得到 $2 \to 3 \to 4 \to 5 \to 6$ 。
然后把 $1$ 和 $2 \to 3 \to 4 \to 5 \to 6$ 连起来，也就是节点 $1$ 的 $right$ 更新为节点 $2$ （即 $root . left$ ），得到 $1 \to 2 \to 3 \to 4 \to 5 \to 6$ 。
最后把 $root . left$ 置为空。

上面的过程，我们需要知道左子树链表的尾节点 $4$ 。所以 DFS 需要返回链表的尾节点。

链表合并完成后，返回合并后的链表的尾节点，也就是右子树链表的尾节点。如果右子树是空的，则返回左子树链表的尾节点。如果左右子树都是空的，返回当前节点。

Python 解法3C++ 解法3

python

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None
        left_tail = self.flatten(root.left)
        right_tail = self.flatten(root.right)
        if left_tail:
            left_tail.right = root.right  # 左子树链表的尾节点 -> 右子树链表的头节点
            root.right = root.left  # root -> 左子树链表的头节点
            root.left = None
        return right_tail or left_tail or root

cpp

// C++ 版待补充

C++ 解法4

cpp

class Solution {
    TreeNode* dfs(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }
        TreeNode* left_tail = dfs(root->left);
        TreeNode* right_tail = dfs(root->right);
        if (left_tail) {
            left_tail->right = root->right; // 左子树链表的尾节点 -> 右子树链表的头节点
            root->right = root->left; // root -> 左子树链表的头节点
            root->left = nullptr;
        }
        return right_tail ? right_tail : left_tail ? left_tail : root;
    }

public:
    void flatten(TreeNode* root) {
        dfs(root);
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 是二叉树的节点个数。
空间复杂度： $O (n)$ 。递归需要 $O (n)$ 的栈空间。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

方法一：头插法 ​

复杂度分析 ​

方法二：分治 ​

复杂度分析 ​

分类题单 ​

方法一：头插法

复杂度分析

方法二：分治

复杂度分析

分类题单