# 114. 二叉树展开为链表

# 题目描述

给你二叉树的根结点 root,请你将它展开为一个单链表:

展开后的单链表应该同样使用 TreeNode,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null。
展开后的单链表应该与二叉树 前序遍历 顺序相同。

示例 1:

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

1
2

示例 2:

输入：root = []
输出：[]

1
2

示例 3:

输入：root = [0]
输出：[0]

1
2

提示:

树中结点数在范围 [0, 2000] 内
-100 <= Node.val <= 100

进阶: 你可以使用原地算法(O(1) 额外空间)展开这棵树吗?

# 思路

题目要求按前序遍历顺序展开成链表,所以首先要理解前序遍历的顺序:根→左→右。

# 方法一:先遍历再重组(额外空间)

最直观的思路:

前序遍历树,把所有节点存到一个数组中
遍历数组,把每个节点的 left 设为 null,right 指向下一个节点

这个方法简单易懂,但空间复杂度 O(n),不符合进阶要求。

# 方法二:递归原地展开(O(1)空间)

能不能在遍历的同时重组指针,不用额外空间呢?

关键是理解递归的本质:递归处理左右子树,然后把它们"拼接"到根节点后面。

具体步骤:

递归展开左子树和右子树
此时左子树已经是一条链,右子树也是一条链
把左子树的链接到根节点的 right
找到左子树链的末尾,把右子树链接在后面
把根节点的 left 设为 null

# 方法三:前序遍历+当场改指针(O(1)空间,最优)

还有一个更巧妙的方法:从右往左,从下往上处理。

用一个变量 prev 记录前序遍历中"上一个访问的节点",然后按右→左→根的顺序递归(前序遍历的倒序):

先递归处理右子树
再递归处理左子树
最后处理根节点:把当前节点的 right 指向 prev,left 设为 null

为什么是倒序?因为我们要让每个节点的 right 指向"前序遍历的下一个节点",倒着处理就能用 prev 记录这个"下一个节点"。

# 模拟过程

以 root = [1,2,5,3,4,null,6] 为例:

1
2
3
4
5

前序遍历顺序:1 → 2 → 3 → 4 → 5 → 6

方法二(递归拼接)的过程:

第一步:递归处理左子树(节点2)

递归展开节点2的左子树(节点3)和右子树(节点4)
把节点3接到节点2的right
把节点4接到节点3的right
左子树展开完成:2 → 3 → 4

第二步:递归处理右子树(节点5)

递归展开节点5的右子树(节点6)
右子树展开完成:5 → 6

第三步:拼接到根节点

把左子树链 2→3→4 接到节点1的right
找到左子树链的末尾(节点4),把右子树链 5→6 接在后面
最终:1 → 2 → 3 → 4 → 5 → 6

drawio 提示词: 画两张图展示递归拼接过程。第一张展示原始树结构,标注前序遍历顺序 1→2→3→4→5→6,用不同颜色区分左子树和右子树。第二张展示拼接过程的三个阶段:左子树递归展开、右子树递归展开、拼接到根节点,用箭头表示指针的重组,最终形成一条右链。两张图画布统一,Logo 放左下角。

文件名:

0114.flatten-binary-tree-01-structure.drawio
0114.flatten-binary-tree-02-recursion-process.drawio

# 解题代码

# 方法二:递归拼接

class Solution {
public:
    void flatten(TreeNode* root) {
        if (root == nullptr) return;
        
        // 递归展开左右子树
        flatten(root->left);
        flatten(root->right);
        
        // 保存右子树
        TreeNode* rightTree = root->right;
        
        // 把左子树移到右边
        root->right = root->left;
        root->left = nullptr;
        
        // 找到当前右子树(原左子树)的末尾
        TreeNode* curr = root;
        while (curr->right != nullptr) {
            curr = curr->right;
        }
        
        // 把原来的右子树接在末尾
        curr->right = rightTree;
    }
};

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

# 方法三:倒序递归(最优)

class Solution {
private:
    TreeNode* prev = nullptr; // 记录前序遍历的上一个节点
    
public:
    void flatten(TreeNode* root) {
        if (root == nullptr) return;
        
        // 倒序:右→左→根
        flatten(root->right);
        flatten(root->left);
        
        // 重组当前节点
        root->right = prev;
        root->left = nullptr;
        prev = root; // 更新prev
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 复杂度分析

时间复杂度:O(n),每个节点访问一次
空间复杂度:O(h),递归栈的深度,h 是树的高度

# 其他语言

# Python3

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        if not root:
            return
        
        # 递归展开左右子树
        self.flatten(root.left)
        self.flatten(root.right)
        
        # 保存右子树
        right_tree = root.right
        
        # 把左子树移到右边
        root.right = root.left
        root.left = None
        
        # 找到当前右子树的末尾
        curr = root
        while curr.right:
            curr = curr.right
        
        # 把原来的右子树接在末尾
        curr.right = right_tree

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

# Java

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        
        // 递归展开左右子树
        flatten(root.left);
        flatten(root.right);
        
        // 保存右子树
        TreeNode rightTree = root.right;
        
        // 把左子树移到右边
        root.right = root.left;
        root.left = null;
        
        // 找到当前右子树的末尾
        TreeNode curr = root;
        while (curr.right != null) {
            curr = curr.right;
        }
        
        // 把原来的右子树接在末尾
        curr.right = rightTree;
    }
}

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

# Go

func flatten(root *TreeNode) {
    if root == nil {
        return
    }
    
    // 递归展开左右子树
    flatten(root.Left)
    flatten(root.Right)
    
    // 保存右子树
    rightTree := root.Right
    
    // 把左子树移到右边
    root.Right = root.Left
    root.Left = nil
    
    // 找到当前右子树的末尾
    curr := root
    for curr.Right != nil {
        curr = curr.Right
    }
    
    // 把原来的右子树接在末尾
    curr.Right = rightTree
}