LeetCode 114. 二叉树展开为链表

2026-06-15 HGNULB 约 5 分钟

文章信息 19 个分类 5 个标签

分类

LeetCode CodeTop 中等已解决 20-50 字节跳动微软美团阿里巴巴快手腾讯猿辅导百度华为小米虾皮携程 LeetCode 热题 100 面试经典 150 题

题目描述

✅ 114. 二叉树展开为链表

题意分析

给定一棵二叉树的根节点，要求把它「展开」成一个单链表，并且是原地展开，直接改动原有节点的指针，不允许新建节点。

展开后的形态有两条硬性要求，缺一不可。第一，链表用 right 指针串联，而每个节点的 left 指针必须置为空。很多人只做到把节点串成一串就交卷，忘了清左指针；由于结果树仍要用 TreeNode 表示，残留的 left 会让判题认为这不是一条链表，直接判错。第二，节点在链表中的先后顺序必须与原树的先序遍历顺序一致，也就是「根、左、右」。选先序不是随意的：正因为先序里根排在最前，展开后整条链的头恰好还是原来的 root，这让原地改指针成为可能。

换个角度看，最终形态其实是一棵每个节点都只有右孩子的「右斜树」。所谓链表，不过是这棵退化的树的另一种叫法。

边界方面，空树直接返回，什么都不用做；单节点树本身已经满足要求；一条已经是右斜的链再展开一次，结果应当不变，这是个很好的自检用例。另外注意题目给的是 void 返回，改动必须落在传入的节点上，重新赋值局部变量是没用的。

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

核心思路

问题关键：展开后的右链必须等于原树的前序遍历，即“根 → 左子树 → 右子树”。处理节点 cur 时，真正的难点不是把左子树移到右边，而是不能因此丢失原右子树。

为什么选择原地迭代：若 cur.left 存在，前序顺序要求整棵左子树排在原右子树之前。沿左子树的右指针找到最右节点 tail，先令 tail.right = cur.right 保存原右子树，再把左子树搬到 cur.right，最后清空 cur.left。整个过程只需要两个指针，不必先用数组保存前序序列，也没有递归栈。

不变量：每轮开始时，cur 之前的右链已经是最终的前序前缀，且这些节点的左指针都为空；以 cur 开始的未处理结构仍保持原前序序列。重连只把“左子树、右子树”改成右链上的先后关系，不改变两棵子树内部的前序顺序。

正确性：重连前当前部分的前序是 cur + preorder(left) + preorder(right)。tail 是左子树右链上最后一个节点，原本没有右孩子；把原右子树接到这里后，前序仍会先走完整棵左子树，再进入原右子树，所以序列不变。同时 cur.left 被清空，cur.right 正好指向下一个前序节点。不断沿 cur.right 前进，最终所有节点按原前序串成右链，所有左指针为空。

反向前序递归也能用一个 pre 指针完成，代码更短，但会占用 $O(h)$ 调用栈；本解法直接满足常数额外空间。

解题步骤

从根节点开始，令 cur = root。

若 cur.left 为空，当前节点无需重连，直接移动到 cur.right。

否则从 cur.left 出发沿 right 找到最右节点 tail。

先令 tail.right = cur.right，保存原右子树；再令 cur.right = cur.left，最后令 cur.left = null。

继续处理新的 cur.right，直到 cur == null。

以 [1,2,5,3,4,null,6] 为例：在节点 1 处找到左子树最右节点 4，把原右子树 5 接到 4 后，再把 2 搬到 1 的右边；随后在节点 2 处把 4 接到 3 后并搬动左子树。最终得到 1 → 2 → 3 → 4 → 5 → 6。

代码实现

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 两个指针，所有连接都复用原节点。

关键点总结

目标顺序来自前序遍历，重连必须保证“整棵左子树在原右子树之前”。

覆盖 cur.right 前，先用 tail.right 接住原右子树，否则节点会丢失。

cur.left = null 是输出结构的一部分，不能只调整右指针。

循环始终沿新的 cur.right 前进，它就是下一个待处理的前序节点。

易错点总结

先写 cur.right = cur.left，再保存原右子树：[1,2,5] 中节点 5 会失去唯一引用。顺序必须是先接 tail.right。

只取 cur.left.right 当尾节点：左子树右链可能不止一层，必须用循环找到真正的最右节点。

忘记清空 cur.left：右链顺序即使正确，结果仍是一棵带左分支的树，不满足题意。

重连后仍沿旧右子树前进：会跳过刚搬来的左子树；应统一执行 cur = cur.right。

把内外两层循环直接判断成 $O(n^2)$：复杂度要看累计访问次数；尾部搜索不会对同一段右链反复回扫，累计仍为 $O(n)$。

相似题目

题目	难度	考察点
897. 递增顺序搜索树	简单	同样拉成右斜树，但顺序改为中序
426. 将二叉搜索树转化为排序的双向链表	中等	中序原地重连，且要维护双向指针并首尾成环
430. 扁平化多级双向链表	中等	同为「子结构整体插入后继之前」，载体换成多级链表
116. 填充每个节点的下一个右侧节点指针	中等	原地连指针但按层横向连接，靠上一层做常数空间遍历
144. 二叉树的前序遍历	简单	只输出先序序列，不改结构，是本题的前置基本功
109. 有序链表转换二叉搜索树	中等	逆向操作：由链表构建平衡树，考察中序与分治的配合