（LeetCodeHot100）114. 二叉树展开为链表——flatten-binary-tree-to-linked-list

zhangzhang2025-12-172025-12-19

114. 二叉树展开为链表——flatten-binary-tree-to-linked-list

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？ked-list

我的思路1ms|击败32.28%

原本想着递归拿到先序序列，再构建这个新的“链表”

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }

        List<TreeNode> nodeList = new ArrayList<>();
        preOrderTraverse(root, nodeList); // 存储节点（而非值，避免新建节点）

        // 基于原节点构建链表（原地修改）
        for (int i = 0; i < nodeList.size() - 1; i++) {
            TreeNode curr = nodeList.get(i);
            TreeNode next = nodeList.get(i + 1);
            curr.left = null;
            curr.right = next; // 原节点的right指向后一个原节点
        }
    }

    // 前序遍历：存储节点（而非值）
    private void preOrderTraverse(TreeNode root, List<TreeNode> nodeList) {
        if (root == null) {
            return;
        }
        nodeList.add(root); // 直接存节点引用，不是值
        preOrderTraverse(root.left, nodeList);
        preOrderTraverse(root.right, nodeList);
    }
}

官方解答

方法一：前序遍历（跟我的一样）

将二叉树展开为单链表之后，单链表中的节点顺序即为二叉树的前序遍历访问各节点的顺序。因此，可以对二叉树进行前序遍历，获得各节点被访问到的顺序。由于将二叉树展开为链表之后会破坏二叉树的结构，因此在前序遍历结束之后更新每个节点的左右子节点的信息，将二叉树展开为单链表。

对二叉树的前序遍历不熟悉的读者请自行练习「144. 二叉树的前序遍历」。

前序遍历可以通过递归或者迭代的方式实现。以下代码通过递归实现前序遍历。

class Solution {
    public void flatten(TreeNode root) {
        List<TreeNode> list = new ArrayList<TreeNode>();
        preorderTraversal(root, list);
        int size = list.size();
        for (int i = 1; i < size; i++) {
            TreeNode prev = list.get(i - 1), curr = list.get(i);
            prev.left = null;
            prev.right = curr;
        }
    }

    public void preorderTraversal(TreeNode root, List<TreeNode> list) {
        if (root != null) {
            list.add(root);
            preorderTraversal(root.left, list);
            preorderTraversal(root.right, list);
        }
    }
}

以下代码通过迭代实现前序遍历。（就是用栈来记录访问过的根节点，以便于访问完左节点之后回到根节点继续访问右节点）

class Solution {
    public void flatten(TreeNode root) {
        List<TreeNode> list = new ArrayList<TreeNode>();
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                list.add(node);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        int size = list.size();
        for (int i = 1; i < size; i++) {
            TreeNode prev = list.get(i - 1), curr = list.get(i);
            prev.left = null;
            prev.right = curr;
        }
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是二叉树的节点数。前序遍历的时间复杂度是 O(n)，前序遍历之后，需要对每个节点更新左右子节点的信息，时间复杂度也是 O(n)。
空间复杂度：O(n)，其中 n 是二叉树的节点数。空间复杂度取决于栈（递归调用栈或者迭代中显性使用的栈）和存储前序遍历结果的列表的大小，栈内的元素个数不会超过 n，前序遍历列表中的元素个数是 n。

方法二：前序遍历和展开同步进行

使用方法一的前序遍历，由于将节点展开之后会破坏二叉树的结构而丢失子节点的信息，因此前序遍历和展开为单链表分成了两步。能不能在不丢失子节点的信息的情况下，将前序遍历和展开为单链表同时进行？

之所以会在破坏二叉树的结构之后丢失子节点的信息，是因为在对左子树进行遍历时，没有存储右子节点的信息，在遍历完左子树之后才获得右子节点的信息。只要对前序遍历进行修改，在遍历左子树之前就获得左右子节点的信息，并存入栈内，子节点的信息就不会丢失，就可以将前序遍历和展开为单链表同时进行。

该做法不适用于递归实现的前序遍历，只适用于迭代实现的前序遍历。修改后的前序遍历的具体做法是，每次从栈内弹出一个节点作为当前访问的节点，获得该节点的子节点，如果子节点不为空，则依次将右子节点和左子节点压入栈内（注意入栈顺序）。

展开为单链表的做法是，维护上一个访问的节点 prev，每次访问一个节点时，令当前访问的节点为 curr，将 prev 的左子节点设为 null 以及将 prev 的右子节点设为 curr，然后将 curr 赋值给 prev，进入下一个节点的访问，直到遍历结束。需要注意的是，初始时 prev 为 null，只有在 prev 不为 null 时才能对 prev 的左右子节点进行更新。

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(root);
        TreeNode prev = null;
        while (!stack.isEmpty()) {
            TreeNode curr = stack.pop();
            if (prev != null) {
                prev.left = null;
                prev.right = curr;
            }
            TreeNode left = curr.left, right = curr.right;
            if (right != null) {
                stack.push(right);
            }
            if (left != null) {
                stack.push(left);
            }
            prev = curr;
        }
    }
}

这个方法的核心是用「栈实现迭代版前序遍历」+「同步维护链表指针（用 prev 节点）」，我用「示例树 + 步骤拆解」的方式给你讲清楚，先看示例树（和题目里的示例 1 一致）：

原树结构：
    1
   / \
  2   5
 / \   \
3   4   6

第一步：先搞懂「栈实现迭代版前序遍历」

前序遍历的顺序是「根 → 左 → 右」，但栈是「后进先出」的结构，所以要先压右子节点，再压左子节点—— 这样弹出时才会先弹出左子节点，保证遍历顺序是「根→左→右」。

比如处理根节点1时：

先弹出根1（处理根）；
再把1的右子节点5压栈，左子节点2压栈（栈内现在是[5,2]）；
下一次弹出的是2（处理左），再压2的右4、左3（栈内[5,4,3]）；
再弹出3（处理左的左）…… 以此类推，最终遍历顺序是1→2→3→4→5→6（符合前序要求）。

第二步：同步展开的核心 ——prev节点的作用

我们需要把遍历到的节点串成链表（左指针 null，右指针指向下一个节点），所以用prev记录「上一个处理过的节点」：

每次处理当前节点curr时，把prev的左指针设为null（链表要求）；
把prev的右指针设为curr（把上一个节点和当前节点连起来）；
再把prev更新为curr，准备处理下一个节点。

复杂度分析

时间复杂度：O(n)，其中 n 是二叉树的节点数。前序遍历的时间复杂度是 O(n)，前序遍历的同时对每个节点更新左右子节点的信息，更新子节点信息的时间复杂度是 O(1)，因此总时间复杂度是 O(n)。
空间复杂度：O(n)，其中 n 是二叉树的节点数。空间复杂度取决于栈的大小，栈内的元素个数不会超过 n。

方法三：寻找前驱节点

前两种方法都借助前序遍历，前序遍历过程中需要使用栈存储节点。有没有空间复杂度是 O(1) 的做法呢？

注意到前序遍历访问各节点的顺序是根节点、左子树、右子树。如果一个节点的左子节点为空，则该节点不需要进行展开操作。如果一个节点的左子节点不为空，则该节点的左子树中的最后一个节点被访问之后，该节点的右子节点被访问。该节点的左子树中最后一个被访问的节点是左子树中的最右边的节点，也是该节点的前驱节点。因此，问题转化成寻找当前节点的前驱节点。

具体做法是，对于当前节点，如果其左子节点不为空，则在其左子树中找到最右边的节点，作为前驱节点，将当前节点的右子节点赋给前驱节点的右子节点，然后将当前节点的左子节点赋给当前节点的右子节点，并将当前节点的左子节点设为空。对当前节点处理结束后，继续处理链表中的下一个节点，直到所有节点都处理结束。

class Solution {
    public void flatten(TreeNode root) {
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left != null) {
                TreeNode next = curr.left;
                TreeNode predecessor = next;
                while (predecessor.right != null) {
                    predecessor = predecessor.right;
                }
                predecessor.right = curr.right;
                curr.left = null;
                curr.right = next;
            }
            curr = curr.right;
        }
    }
}