LeetCode 面试题 17.12. BiNode

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

题目描述

✅ 面试题 17.12. BiNode

image-20260929105930863

题意分析

将二叉搜索树原地改成按节点值升序排列的单向右链：复用原节点，所有左指针置空，右指针指向排序后的下一节点，返回链头。二叉搜索树的中序遍历恰好给出所需顺序。

解法：中序遍历 + 原地右链

核心思路

[!blue]

使用显式栈执行中序遍历：游标 cur 沿左链不断压栈，无法再向左时弹出一个节点，这就是尚未访问的最小节点。它的左子树已经处理完，接下来才轮到它自身和右子树。

用 head 记录首个访问节点，prev 记录已访问序列的尾节点。每次弹出 node，先清空其左指针；若它是首节点就设置 head，否则令 prev.right = node，把它接到已有前缀后面，再更新 prev。由中序顺序保证，每次追加后已连接前缀仍然有序。

原地改链接不会丢掉未访问部分。清空 node.left 时，左子树已经全部访问；修改的是前驱 prev 的右指针，当前 node 的原右子树入口仍未改变，可以继续令 cur = node.right。前驱原右子树的搜索也已经由此前的游标和栈接管，不再依赖被改写的前驱链接。

每个节点最终都作为当前节点清空左指针，并在下一节点到来时连接右后继。最后访问的是最大节点，它原本就没有右子树，因此链尾自然为空，不需要额外创建节点或哨兵。

解题步骤

  1. 初始化空栈，cur = root，head、prev 为空。
  2. 只要游标非空就沿左链压栈；到达空位置后弹出下一个中序节点。
  3. 清空当前节点左指针，设置链头或连接前驱，然后将 prev 移到当前节点。
  4. 让游标进入当前节点的原右子树，重复以上过程，直到游标和栈都为空，返回 head。空树不会进入循环，直接返回空。

代码实现

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)$。每个节点入栈、出栈各一次，重连指针只需常数时间。
  • 空间复杂度：$O(h)$。显式栈深度由树高 h 决定，最坏链状树为 $O(n)$；结果复用原节点。

关键点总结

[!green]

  • 中序访问顺序决定链表顺序，head 和 prev 分别保存已连接前缀的头尾。
  • 左子树处理完才清空左指针，当前右子树入口读取后继续遍历。
  • 必须先用旧 prev 连接当前节点，再更新 prev，不能把前驱和当前节点混成同一个对象。

易错点总结

[!yellow]

  • 还没沿左链下降就清空左指针，会切断未访问子树。
  • 先令 prev = node 再写 prev.right = node，会把当前节点连向自身。
  • 忘记更新 prev，后续节点无法依次接入完整右链。
  • 返回原根可能漏掉更小节点，必须返回中序首节点 head。
  • 只检查游标是否为空就结束，会丢掉栈中尚待处理的祖先。

相似题目

题目 难度 关联与区别
114. 二叉树展开为链表 中等 同样原地连成链，本题按BST中序成为递增右链，原题按前序展开普通二叉树。
426. 将二叉搜索树转化为排序的双向链表 中等 同样按BST中序重连节点，原题连接为循环双向链表，本题只保留向右的单链。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/44979257
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！