LeetCode 114. 二叉树展开为链表

约 5 分钟
文章信息 19 个分类 5 个标签
分类
LeetCode CodeTop 中等 已解决 20-50 LeetCode 热题 100 面试经典 150 题 腾讯 字节 阿里 华为 微软 美团 小米 百度 快手 携程 虾皮 猿辅导
标签
深度优先搜索 树 二叉树 栈 链表

题目描述

✅ 114. 二叉树展开为链表

image-20260928204008880

image-20260928204008881

题意分析

将原二叉树展开成一条只沿右指针连接的链，节点顺序必须与原树的前序遍历一致，即根、左子树、右子树。所有左指针都要置空，并且直接复用原节点，不创建另一条链表。

对每个当前节点，都要让整棵原左子树排在原右子树之前。难点是移动左子树时保住原右子树，并把它放在正确的后续位置，而不是覆盖右指针后丢失这一部分节点。

解法：原地迭代重连左右子树

核心思路

[!blue]

沿最终右链逐个处理节点 cur。已经走过的前缀顺序正确且左指针为空，cur 是下一个应按前序访问的节点。如果它没有左子树，下一步直接沿右指针继续即可；有左子树时，下一节点必须先进入这棵左子树。

在覆盖 cur.right 之前，先为原右子树寻找后续连接点：从 cur.left 出发，只沿右指针走到最右节点 tail，此时它没有右孩子，把 cur.right 接到 tail.right。然后让 cur.right = cur.left，将左子树移到当前位置之后，最后清空 cur.left。

为什么能接到这个最右节点？沿右链向下时，链上每个节点的左子树在前序中都先于其右子树处理；走到最后的 tail 后，即使它还有左子树，也会先访问这部分左后代，再进入新接上的右子树。因此原右子树仍排在整棵原左子树之后，没有改变前序顺序。

这里并没有一次把左子树全部展开，tail 也未必是叶子或原左子树前序的最后一个节点。连接只是保留了正确的待处理顺序；接下来令 cur = cur.right，进入刚移来的左子树，后续循环会继续消除其中的左分支。

每次重连都先保存原右子树，再移动左子树，不会丢失节点；每个处理过的节点又被清空左指针。最终沿右链走到空时，全部节点都按原前序连接起来，所有左连接也都已清除。

解题步骤

  1. 从根节点开始，令 cur = root。
  2. 若 cur.left 为空，直接继续处理 cur.right。
  3. 否则从 cur.left 出发，沿右指针找到没有右孩子的节点 tail。
  4. 依次执行 tail.right = cur.right、cur.right = cur.left、cur.left = null，先接住原右子树再移动左子树。
  5. 沿新的 cur.right 前进，重复到 cur 为空。

代码实现

class Solution {
    public void flatten(TreeNode root) {
        for (TreeNode cur = root; cur != null; cur = cur.right) {
            if (cur.left == null) {
                continue;
            }

            TreeNode tail = cur.left;

            while (tail.right != null) {
                tail = tail.right;
            }

            // 先把原右子树接到左子树最右端，避免移动左子树时丢失它。
            tail.right = cur.right;
            cur.right = cur.left;
            // 左子树已移到右侧，清空左连接以满足单链展开要求。
            cur.left = null;
        }
    }
}

func flatten(root *TreeNode) {
    for cur := root; cur != nil; cur = cur.Right {
        if cur.Left == nil {
            continue
        }

        tail := cur.Left
        for tail.Right != nil {
            tail = tail.Right
        }

        // 先把原右子树接到左子树最右端，避免移动左子树时丢失它。
        tail.Right = cur.Right
        cur.Right = cur.Left
        // 左子树已移到右侧，清空左连接以满足单链展开要求。
        cur.Left = nil
    }
}

复杂度分析

  • 时间复杂度：$O(n)$。外层依次处理每个节点；寻找 tail 时走过的右指针不会在后续的左子树尾部搜索中重复扫描，总操作数与节点数同阶。
  • 空间复杂度：$O(1)$。只使用 cur 和 tail 两个指针，所有连接都复用原节点。

关键点总结

[!green]

  • 目标顺序来自前序遍历，重连必须保证“整棵左子树在原右子树之前”。
  • 覆盖 cur.right 前，先用 tail.right 接住原右子树，否则节点会丢失。
  • cur.left = null 是输出结构的一部分，不能只调整右指针。
  • 循环始终沿新的 cur.right 前进，它就是下一个待处理的前序节点。

易错点总结

[!yellow]

  • 先覆盖当前右指针：必须先把原右子树接到 tail.right，否则可能失去它的入口。
  • 把左子树根的右孩子直接当作末端：右链可能有多层，也可能根本没有右孩子，应循环找到真正的最右节点。
  • 忘记清空左指针：即使右链顺序正确，结果仍带有左分支，不满足题意。
  • 重连后沿原右子树继续：会跳过尚未展开的左子树，应沿新的 cur.right 前进。
  • 把 tail 当成已经展开的链尾：它可能仍有左后代，后续循环还需要继续处理这些分支。

相似题目

题目 难度 关联与区别
430. 扁平化多级双向链表 中等 同样按深度优先顺序展平层级结构，原题多级双向链表还需维护prev与清空child。
897. 递增顺序搜索树 简单 同样把树连成右链，本题按前序顺序，原题按BST中序顺序形成递增链。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/74081092
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！