算法

展开二叉树

loser

29 Aug 2026 • 11 min read

给你二叉树的根节点 root，请你将它展开为一个单链表。

展开后的单链表继续使用 TreeNode，其中 right 子指针指向链表中的下一个节点，left 子指针始终为 nullptr。
展开后的单链表顺序应该和二叉树的先序遍历顺序相同。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

进阶： 可以使用原地算法，即只使用 O(1) 额外空间展开这棵树吗？

解法一（递归反向先序遍历）：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    TreeNode* previous = nullptr;

public:
    void flatten(TreeNode* root) {
        if (root == nullptr)
        {
            return;
        }

        flatten(root->right);
        flatten(root->left);

        root->right = previous;
        root->left = nullptr;
        previous = root;
    }
};

解法二（迭代原地展开）：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* current = root;

        while (current != nullptr)
        {
            if (current->left != nullptr)
            {
                TreeNode* predecessor = current->left;

                while (predecessor->right != nullptr)
                {
                    predecessor = predecessor->right;
                }

                predecessor->right = current->right;
                current->right = current->left;
                current->left = nullptr;
            }

            current = current->right;
        }
    }
};

核心思想

题目要求展开后的链表顺序和先序遍历顺序相同。

先序遍历顺序是：

根节点 -> 左子树 -> 右子树

所以对于当前节点 root，展开后的顺序应该是：

root -> flatten(root->left) -> flatten(root->right)

关键在于，展开过程中不能丢失原来的右子树。

可以先把当前节点的左子树展开，再把原来的右子树接到左子树展开结果的末尾。

这题最关键的观察是：

当前节点的左子树展开后，左子树中先序遍历的最后一个节点，就是整个左子树链表的尾节点。

因此可以执行以下操作：

找到当前节点左子树中最右侧的节点，也就是左子树先序展开后的尾节点。
把当前节点原来的右子树接到这个尾节点后面。
把当前节点的左子树整体移到右边。
把当前节点的左指针置为 nullptr。

这样就完成了当前节点的局部调整，并且没有创建新节点。

解法一：递归反向先序遍历

如果按照正常先序遍历访问节点，需要先处理当前节点，再处理左子树和右子树。

但当前节点要连接到“先序遍历中的下一个节点”，这个下一个节点只有在左子树和右子树处理完成后才容易确定。

因此可以反过来处理先序遍历：

右子树 -> 左子树 -> 根节点

这相当于先序遍历序列的逆序。

用 previous 保存当前节点在展开链表中的后继节点。

递归处理顺序是：

flatten(root->right);
flatten(root->left);

处理完成后，previous 正好指向当前节点在先序序列中的下一个节点。

于是把当前节点接到 previous 前面：

root->right = previous;
root->left = nullptr;
previous = root;

最终所有节点都会按照先序顺序通过 right 指针连接起来。

为什么递归时要先处理右子树

假设先序遍历顺序是：

根 -> 左 -> 右

那么逆序就是：

右 -> 左 -> 根

例如这棵树：

先序遍历顺序是：

1,2,3,4,6,5

逆序处理顺序是：

5,6,4,3,2,1

处理 5 时，它的后继为空。

处理 6 时，把 6->right 指向 5。

处理 4 时，把 4->right 指向 6。

依次处理后，previous 最终会形成：

1 -> 2 -> 3 -> 4 -> 6 -> 5

所以“先右后左”的递归顺序，是为了从后往前建立先序链表。

解法二：迭代原地展开

迭代解法不使用递归，也不使用额外容器。

用 current 从根节点开始，沿着最终链表的 right 指针向后移动。

如果当前节点没有左子树，那么它已经符合链表结构，直接移动到右孩子。

如果当前节点有左子树，就需要把左子树插入到当前节点和原右子树之间。

假设当前结构是：

current
   /   \
 left  right

处理后要变成：

current -> left 子树展开结果 -> right 子树

左子树先序遍历的最后一个节点，是左子树中最右侧的节点。

因此先找到它：

TreeNode* predecessor = current->left;

while (predecessor->right != nullptr)
{
    predecessor = predecessor->right;
}

然后执行三步指针调整：

predecessor->right = current->right;
current->right = current->left;
current->left = nullptr;

第一步保存原来的右子树。

第二步把左子树移到右侧，符合先序顺序。

第三步清空左指针，满足单链表要求。

完成后继续处理：

current = current->right;

为什么左子树最右节点是展开后的尾节点

对一棵子树进行先序遍历时，顺序是：

根节点 -> 左子树 -> 右子树

因此，先序遍历的最后一个节点一定位于这棵子树的最右侧路径上。

在当前局部结构中，左子树还没有被移动之前，它的最右侧节点就是左子树先序展开结果的尾节点。

把当前节点原来的右子树接到这个节点后面，就能得到：

当前节点 -> 左子树先序序列 -> 原右子树先序序列

这正好是当前子树的先序序列。

为什么不会丢失原来的右子树

如果直接执行：

current->right = current->left;

原来的右子树指针就会被覆盖，导致右子树丢失。

所以必须先把原来的右子树保存到左子树展开结果的尾部：

predecessor->right = current->right;

此时原右子树仍然可以从 predecessor 访问到。

之后再执行：

current->right = current->left;

就不会丢失任何节点。

边界情况

如果二叉树为空：

root = []

没有节点需要展开，直接返回。

如果二叉树只有一个节点，它没有左右孩子，展开后仍然是这个节点，左指针为 nullptr。

如果当前节点只有左子树，左子树会被移动到右侧，原来的右指针为空。

如果当前节点只有右子树，没有左子树，不需要调整，直接继续处理右子树。

如果树退化成一条左链，每次都会把左孩子移动到右边，最后得到一条从上到下的右链。

如果树退化成一条右链，原结构已经符合先序展开结果，不需要修改。

正确性证明

我们证明：两个解法都能将二叉树原地展开为符合先序遍历顺序的单链表。

结论 1：递归解法处理节点时，`previous` 保存其先序后继

设当前节点为 root。

递归先处理 root 的右子树，再处理左子树，最后处理 root。

这正是先序序列：

root -> 左子树 -> 右子树

的逆序。

因此，当处理 root 时，先序序列中位于 root 后面的所有节点都已经通过 right 指针连接好，并且链表头节点就是 previous。

所以 previous 正好是 root 在先序序列中的后继节点。

结论 2：递归解法连接出的顺序是先序顺序

处理当前节点时，算法执行：

root->right = previous;
root->left = nullptr;
previous = root;

这会把当前节点放到已经构造好的后继链表前面。

由于节点是按照先序序列的逆序被处理，所以每次把当前节点放到前面后，链表顺序就恢复为先序顺序。

因此最终链表节点顺序和原树的先序遍历顺序相同。

结论 3：迭代解法的局部调整不会改变当前子树的先序顺序

考虑当前节点 current。

它原来的先序顺序是：

current -> 左子树 -> 右子树

如果存在左子树，算法找到左子树最右侧节点 predecessor，并执行：

predecessor->right = current->right;
current->right = current->left;
current->left = nullptr;

调整后，从 current 沿 right 指针访问到的顺序变为：

current -> 左子树 -> 原右子树

左子树和右子树内部的相对顺序没有改变。

所以当前子树的先序顺序保持不变。

结论 4：迭代解法不会丢失任何节点

在修改当前节点之前，算法先将原来的右子树连接到左子树的尾节点：

predecessor->right = current->right;

因此原右子树仍然可以从当前节点的新 right 链路访问到。

左子树则通过：

current->right = current->left;

移动到当前节点右侧。

最后只把已经转移的左指针置空，不删除任何节点。

因此每个原节点都会保留下来，不会丢失。

结论 5：最终所有节点的左指针都为空

递归解法在处理每个节点时都会执行：

root->left = nullptr;

迭代解法在把左子树移动到右侧后，也会执行：

current->left = nullptr;

每个节点都会被处理一次。

所以最终所有节点的左指针都为空。

得出结论

由结论 1 和结论 2 可知，递归解法能按照先序顺序连接所有节点。

由结论 3 可知，迭代解法每次局部调整都保持先序顺序。

由结论 4 可知，迭代调整不会丢失任何节点。

由结论 5 可知，最终所有节点都满足左指针为空的单链表要求。

因此两个解法都能正确完成二叉树展开。

举例理解

以：

root = [1,2,5,3,4,null,6]

为例，这棵树可以理解为：

原树的先序遍历顺序是：

1,2,3,4,5,6

使用迭代原地展开：

处理节点 `1`

节点 1 有左子树。

左子树最右侧节点是 4。

先把原右子树 5 接到 4 后面：

4 -> 5

再把左子树移动到 1 的右侧：

1 -> 2 -> 3/4 -> 5 -> 6

并将 1->left 置空。

处理节点 `2`

节点 2 仍有左子树，左子树最右侧节点是 3。

把 2 的原右子树 4 接到 3 后面，再把左子树移动到右侧：

2 -> 3 -> 4

处理后续节点

节点 3 和 4 没有左子树，直接向右移动。

最终得到：

1 -> 2 -> 3 -> 4 -> 5 -> 6

所有节点的左指针都为空。

复杂度分析

设二叉树节点数为 n，树的高度为 h。

解法一

每个节点只会被递归访问一次。

时间复杂度：O(n)
空间复杂度：O(h)

空间复杂度来自递归调用栈。

解法二

每个节点都会沿着最终的 right 链路被处理一次。

寻找左子树最右节点时，树中的指针会被有限次访问，所有遍历操作的总复杂度为 O(n)。

时间复杂度：O(n)
空间复杂度：O(1)

解法二不使用递归栈，也不创建数组或其他辅助节点，满足题目的进阶要求。