LeetCode 面试题 17.12. BiNode

约 10 分钟
文章信息 7 个分类 6 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 微软 程序员面试金典（第 6 版）
标签
深度优先搜索 树 二叉树 栈 链表 二叉搜索树
目录

题目描述

✅ 面试题 17.12. BiNode

题意分析

给定一棵二叉搜索树的根节点，要求把它就地改造成一个单向链表：用节点的 right 指针充当链表的 next，所有节点的 left 指针必须置空，链表中元素的顺序要与原树的中序遍历顺序一致。返回改造后链表的头节点。

约束里最关键的一句是"不用创建新的节点"。这直接否掉了"先中序遍历收集节点值、再新建一串节点"的做法，要求必须在原有节点上改指针。既然是原地改造，就必须警惕一个风险：改指针的动作会破坏尚未遍历的树结构。比如把某个节点的 right 指向它的中序后继时，如果它原本的右子树还没被访问，这一改就把整棵右子树丢了。

第二个信号是"顺序与中序遍历一致"。因为输入是 BST，中序遍历恰好是升序，所以最终链表也是升序的——但注意题目要的是"中序顺序"这个结构性质，即便换成普通二叉树这套做法也成立，BST 只是让结果额外具备了有序性。

边界上要覆盖：空树（返回空）；只有一个节点（返回它自己，且 left 要置空）；退化成左链或右链的树；以及必须保证返回的是链表头（中序第一个节点，即整棵树的最左节点），而不是原来的根。

解法：迭代中序遍历 + 指针串联

核心思路

暴力做法是先跑一遍中序遍历把节点存进列表，再顺序把它们串起来。它正确且好写，但要额外的 $O(n)$ 列表，而且面试官通常会追问"能不能不用额外容器"。更重要的是，它掩盖了本题真正的考点——在遍历过程中修改结构而不破坏遍历本身。

关键观察是：中序遍历访问一个节点时，它的左子树已经完全处理完毕，而右子树还没开始。所以在这个时刻：

  • 把 node.left 置空是安全的，因为左子树的信息已经不再需要；
  • 把前驱节点的 right 指向 node 也是安全的，因为前驱节点的右子树在中序里恰好排在它之后、node 之前，而中序遍历的性质保证"前驱的右子树"要么为空、要么早已被走完（前驱是 node 的中序前驱，意味着 node 就是前驱之后紧接着要访问的节点）；
  • 但不能在这个时刻改 node.right，因为它的右子树还没被访问。

于是把状态定义为三个指针：prev 指向已经串好的链表的尾节点（即当前节点的中序前驱），head 指向链表头（第一个被访问的节点），cur 是遍历游标。不变量是：每次处理完一个中序位置为 k 的节点后，中序前 k+1 个节点已经通过 right 串成一条链，链头是 head、链尾是 prev，且这条链上所有节点的 left 都已置空。

维持不变量的动作只有三步，在每次"访问"节点时执行：先 node.left = null；再判断 prev 是否为空——为空说明这是中序第一个节点，记 head = node，否则 prev.right = node 把它接到链尾；最后 prev = node 把链尾后移。

为什么这套改动不会破坏遍历？因为迭代中序遍历用显式栈保存了"还没处理的祖先"，而右子树的入口在处理完当前节点后立刻被读出（cur = node.right）并转交给下一轮——先取出 node.right 再让它被后续的 prev.right 覆盖，顺序上刚好错开。这也是为什么选迭代而不是递归：递归写法同样可行，但栈帧里隐含的状态不那么直观，面试里讲解迭代版更容易把"何时改指针是安全的"说清楚。

解题步骤

  • 初始化 stack 为空、cur = root、head = null、prev = null。head 和 prev 都从空开始，这让"第一个节点"这个特殊情形可以靠 prev == null 判断出来，不需要额外的布尔标志。
  • 外层循环条件是 cur != null || !stack.isEmpty()。两个条件缺一不可：cur 非空说明还有子树要下探；栈非空说明还有祖先等待处理。只写其中一个，会在"当前分支走到底但栈里还有节点"时提前退出。
  • 内层循环把左链全部压栈：while (cur != null) { stack.push(cur); cur = cur.left; }。这是标准中序的"一路向左"，压栈顺序保证了最先弹出的是最左节点，也就是中序第一个。
  • 弹栈得到当前要访问的节点 node。此刻它的左子树已经处理完毕，可以安全修改。
  • node.left = null。必须在这里置空。若留到最后统一处理，就得再遍历一次；若提前在压栈时置空，会把还没走完的左子树整个丢掉。
  • prev == null 时记 head = node，否则 prev.right = node。这一步把节点接进链表。head 只会在第一次被赋值，之后 prev 恒非空。
  • prev = node 把链尾后移，维持不变量。
  • cur = node.right 转向右子树。这一行必须写在 prev.right = node 之前不受影响的位置——实际上它在下一轮才会被后继的赋值覆盖，因为 node.right 的值已经被读进 cur 了。这正是整段代码最微妙的地方：读取发生在覆盖之前。
  • 循环结束返回 head。空树时 head 保持为 null，恰好是正确答案。

以下面这棵 BST 走一遍：根 4，左孩子 2（其左孩子 1、右孩子 3），右孩子 5。中序序列是 1, 2, 3, 4, 5。

初始：cur = 4，栈空，head = prev = null。

第 1 轮：内层一路向左，依次压入 4、2、1，cur 变成空。弹出 1。1.left = null（本来就空）。prev 为空 → head = 1。prev = 1。cur = 1.right = null。

第 2 轮：cur 为空但栈非空（栈里还有 4、2）。内层不执行。弹出 2。2.left = null——注意此刻 2 的左孩子 1 已经处理完了，断开安全。prev = 1 非空 → 1.right = 2。prev = 2。cur = 2.right = 3。关键点：这一行先把 3 读进 cur，下一轮 2.right 才会被重新赋值；如果顺序反了，右子树 3 就永远丢失了。

第 3 轮：内层把 3 压栈，cur = 3.left = null。弹出 3。3.left = null。2.right = 3（恰好与原值相同）。prev = 3。cur = 3.right = null。

第 4 轮：栈里还有 4。弹出 4。4.left = null（断开左子树 2，此时 2 已在链上）。3.right = 4。prev = 4。cur = 4.right = 5。

第 5 轮：压入 5，cur 变空。弹出 5。5.left = null。4.right = 5。prev = 5。cur = 5.right = null。

第 6 轮：cur 为空且栈空，循环结束。返回 head = 1。

最终链表沿 right 依次是 1 → 2 → 3 → 4 → 5，所有 left 都为空，与中序序列一致。特别注意返回的是 1 而不是原根 4——链表头是中序第一个节点，也就是整棵树的最左节点。

代码实现

class Solution {
    public TreeNode convertBiNode(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        TreeNode head = null;
        TreeNode prev = null;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();

            node.left = null;
            if (prev == null) {
                head = node;
            } else {
                prev.right = node;
            }
            prev = node;

            cur = node.right;
        }
        return head;
    }
}

func convertBiNode(root *TreeNode) *TreeNode {
    var stack []*TreeNode
    cur := root
    var head *TreeNode
    var prev *TreeNode

    for cur != nil || len(stack) > 0 {
        for cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        }
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        node.Left = nil
        if prev == nil {
            head = node
        } else {
            prev.Right = node
        }
        prev = node

        cur = node.Right
    }
    return head
}

复杂度分析

  • 时间复杂度：$O(n)$，n 为节点数。每个节点恰好入栈一次、出栈一次，出栈时只做常数次指针赋值；没有任何节点被重复访问。
  • 空间复杂度：$O(h)$，h 为树高，来自显式栈中同时保存的祖先节点。平衡树是 $O(\log n)$，退化成左链时是 $O(n)$。相比"先收集节点再串联"的做法，省掉了那个 $O(n)$ 的列表；若追求 $O(1)$ 空间，可以改用 Morris 中序遍历。

关键点总结

  • 中序遍历访问某节点时，"左子树已完成、右子树未开始"是所有原地改造的依据。改 left 安全、接前驱安全、改 right 危险——先把这条时序说清楚，代码里每一行的位置就都有了理由。
  • 需要"前一个元素"时，用一个 prev 指针跟随遍历。这是中序类题目的通用配件：判 BST 合法性、求相邻最小差、转双向链表、本题的串联，用的都是同一个 prev。配合 prev == null 判断首元素，还能省掉额外的标志位。
  • 改指针前先把要用的值读出来。cur = node.right 必须在 node.right 被后续赋值覆盖之前执行。凡是原地修改链式结构，都要机械检查一遍"我改的这个字段，后面还有人要读吗"。
  • 返回值是遍历的第一个元素，不是输入的根。原地改造类题目里，"入口"往往会变，务必单独用一个 head 记录，并让它的初始值（空）恰好等于空输入时的正确答案。
  • 面试视角：主动给出递归、迭代、Morris 三个层次。递归最短但空间 $O(h)$ 且隐式；迭代显式、便于讲清时序；Morris 用线索化把空间压到 $O(1)$，是加分项。稳妥答法是先写迭代版并解释"为什么这时候改指针是安全的"，再补一句"如果要求 $O(1)$ 额外空间，可以用 Morris 中序，代价是要临时修改再恢复右指针"。

易错点总结

  • 错误写法：返回 root 而不是 head → 用例：树 [4, 2, 5, 1, 3]：返回节点 4，但链表头应该是 1，判题拿到的链表只有 4 → 5，丢失了前三个节点。
  • 错误写法：cur = node.right 写在 prev.right = node 之后，且 prev 恰好就是 node（自赋值场景） → 更常见的等价错误是把两行顺序写成先给当前节点的 right 赋值再读取：用例树 [2, 1, 3]：处理完 2 后 2.right 已被指向下一个节点，原来的右子树 3 再也找不到，输出链表变成 1 → 2，丢了 3。
  • 错误写法：在压栈时就置空 left → 用例：树 [2, 1]：压入 2 时把 2.left 置空，内层循环下一步 cur = cur.left 读到空，节点 1 从未被访问，输出链表只有 2。置空必须发生在该节点被"访问"（出栈）之时。
  • 错误写法：忘记 node.left = null → 用例：树 [4, 2, 5, 1, 3]：链表串好了但每个节点的 left 仍指向原来的左孩子，判题按"left 必须为空"校验会直接失败；某些判题还会因为存在环状引用而无限打印。
  • 错误写法：外层循环条件只写 cur != null → 用例：树 [2, 1]：处理完 1 后 cur = 1.right = null，循环立刻结束，栈里的 2 从未被处理，返回的链表只有 1。
  • 错误写法：外层循环条件只写 !stack.isEmpty() → 用例：树 [1, null, 2]：第一轮压入 1 后弹出、cur = 2，此时栈已空，循环结束，节点 2 未被处理。两个条件必须用 || 连接。
  • 错误写法：用 prev.right = node 但忘了更新 prev = node → 用例：树 [4, 2, 5, 1, 3]：所有后续节点都被接到同一个 prev 后面，prev.right 被反复覆盖，最终链表只剩 1 → 5。
  • 错误写法：用 head == null 代替 prev == null 判断首元素 → 本题两者等价，但若树的第一个节点恰好是需要跳过的哨兵（在变体题中常见），head 已被赋值而 prev 语义不同，逻辑会错位。判断"是不是第一个被接入链表的节点"应当看链尾指针。
  • 错误写法：改成先序遍历串联 → 用例：树 [4, 2, 5, 1, 3]：得到 4 → 2 → 1 → 3 → 5，不是中序序列 1, 2, 3, 4, 5，判题失败。题目明确要求中序顺序。
  • 错误写法：Go 里 var stack []*TreeNode 后用 stack[0] 取栈顶 → 用例：任意有两层以上的树：取到的是栈底而不是栈顶，遍历顺序完全错乱。切片模拟栈时栈顶是 stack[len(stack)-1]。
  • 错误写法：Go 里 head := &TreeNode{} 当哨兵却直接返回它 → 用例：空树：返回一个值为 0 的假节点而不是 nil；非空树时返回的链表头也多出一个无效节点。若要用哨兵简化逻辑，最后必须返回 dummy.Right。
  • 错误写法：先中序收集所有节点到列表，再新建一串节点串起来 → 违反"不用创建新的节点"的题目要求；即使判题只比较值序列能通过，面试里也会被要求改成原地版本。

相似题目

题目 难度 考察点
897. 递增顺序搜索树 简单 与本题几乎同构，常用哑节点简化"第一个节点"的分支
114. 二叉树展开为链表 中等 展开顺序是先序而非中序，改指针的安全时机随之完全不同
426. 将二叉搜索树转化为排序的双向链表 中等 要同时维护前驱和后继两个方向，最后还要把首尾接成环
94. 二叉树的中序遍历 简单 纯遍历不改结构，是本题迭代骨架的来源，也是练 Morris 的入口
173. 二叉搜索树迭代器 中等 把同一套显式栈拆成可暂停的迭代器接口，考均摊复杂度分析
面试题 04.05. 合法二叉搜索树 中等 同样用 prev 跟随中序遍历，但只做比较不改结构