LeetCode 897. 递增顺序搜索树

2021-07-10 HGNULB 约 9 分钟

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

分类

题目描述

✅ 897. 递增顺序搜索树

题意分析

给一棵二叉搜索树，把它改造成一棵「只往右长」的树：新树最左（也就是最上）的节点是原树中值最小的节点，每个节点都没有左孩子，只有一个右孩子，整体形如一条递增的链表。返回这条链的头。

二叉搜索树的定义直接给出了答案的顺序：中序遍历 BST 得到的就是升序序列。题目要的链恰好是这个升序序列，所以本题不需要排序、不需要比较大小，只需要按中序顺序把节点重新串起来。

需要看清的是「改造」而不是「新建」——题目允许返回一棵新树，但主流做法是原地重连指针，不额外创建节点。这也带来了本题唯一的技术难点：在遍历过程中修改指针，必须保证还没访问的部分不被破坏。一个节点的 left 被置空之前，它的左子树必须已经处理完；它的 right 被改写之前，原来的右子树必须已经被保存下来。

约束里节点数最多 100，值范围 0 到 1000，规模极小，$O(n)$ 时间和 $O(n)$ 空间都毫无压力。规模小意味着这题考的不是效率，而是指针操作的严谨性。

边界：只有一个节点时返回它自己（且要保证它的 left 被置空）；树退化成左链时结果要完全反向成右链；树本来就是右链时结果与原树一致。

解法：迭代中序遍历 + 尾插重连指针

核心思路

最省事的想法是先中序遍历收集所有节点值到一个列表，再按列表新建一串只有右孩子的节点。这能过，但它绕开了本题真正的考点——原地指针重排，面试官几乎一定会追问「能不能不新建节点」。

换成原地做法，第一个陷阱立刻出现：如果在中序访问到某节点时就写 node.left = null; tail.right = node;，那么 node 原来的右子树指针会被后续的 tail.right = 下一个节点 覆盖掉，还没遍历的右子树就丢了。

由此得到关键做法：先把 node.right 存进遍历用的游标，再改写它。中序遍历本身就要求「访问完当前节点后转向右子树」，所以只要严格按「弹栈 → 保存右孩子 → 重连指针」的顺序写，遍历需要的信息在被破坏前就已经取走了。

具体用标准的迭代中序：一个显式栈加一个游标 cur。内层循环把 cur 沿左链一路压栈直到空，此时栈顶就是当前未访问节点中最小的那个；弹出它、把 cur 指向它的右孩子，然后才做重连。

重连用「哨兵 + 尾指针」：dummy 是一个不参与结果的假头，tail 始终指向已构建链的最后一个节点。每访问一个节点就 node.left = null（新树不能有左孩子）、tail.right = node（挂到链尾）、tail = node（尾指针后移）。

不变量：每次弹栈处理完一个节点后，dummy.right 开始的这条链恰好是「中序序列中已访问过的那些节点」按升序串成的、只含右指针的链，且 tail 指向链尾；同时 cur 与栈中元素合起来，恰好覆盖所有尚未访问的节点，且这些节点的 left/right 指针都还是原样。

哨兵的价值在于免掉「链是否为空」的判断：第一个节点也走 tail.right = node 这条统一路径，最后返回 dummy.right 即真正的头。

解题步骤

初始化 stack、cur = root、dummy = new TreeNode(0)、tail = dummy：dummy 的值任意，它只是个挂钩，永远不会出现在返回结果里。tail 初始指向 dummy，让首个节点的挂接与后续节点写法完全一致。

外层循环 cur != null || !stack.isEmpty()：两个条件缺一不可。只判 cur 会在弹栈后 cur 为空时提前退出，漏掉栈里剩余的节点；只判栈非空会在最开始栈为空时一次都不进循环。

内层沿左链压栈：while (cur != null) { stack.push(cur); cur = cur.left; }。中序要求先处理最左，压栈的过程就是记住「回来时还要访问谁」。

弹栈得到当前最小节点 node：栈顶必然是所有未访问节点中中序最靠前的那个。

立刻执行 cur = node.right：这一行必须排在任何指针改写之前。它既是中序遍历的推进（访问完 node 后转向右子树），也是对 node.right 的抢救性保存——下一轮 tail.right = 下一个节点 会把这个字段覆盖掉。

重连三连：node.left = null、tail.right = node、tail = node。置空 left 是题目的硬性要求（新树不能有左孩子），而且此时 node 的左子树早已遍历完毕，置空不丢信息。三行的顺序里，tail = node 必须在 tail.right = node 之后，先移尾指针会让节点挂到自己身上形成自环。

返回 dummy.right：不是 dummy，也不是 root——原来的根在新树里通常在中间位置。

以 root = [5,3,6,2,4,null,8,1] 走一遍。树的形状：根 5，左孩子 3、右孩子 6；3 的左孩子 2、右孩子 4；2 的左孩子 1；6 的右孩子 8。中序序列是 1, 2, 3, 4, 5, 6, 8。

初始 cur = 5，tail = dummy，栈空。

内层沿左链压栈：压 5、压 3、压 2、压 1，cur 变成 null（1 没有左孩子）。栈自底向上是 [5, 3, 2, 1]。

第 1 次弹栈：node = 1，cur = 1.right = null。重连：1.left = null（本来就是空），dummy.right = 1，tail = 1。链：1。

第 2 次：cur 为空且栈非空，跳过内层，弹出 node = 2，cur = 2.right = null。重连：2.left = null（切断对 1 的引用，而 1 已经在链上了），1.right = 2，tail = 2。链：1 → 2。

第 3 次：弹出 node = 3，cur = 3.right = 4。注意这一步的顺序：先把 4 存进 cur，再执行 3.left = null、2.right = 3、tail = 3。如果先做重连，第 4 轮的 tail.right = 4 会把 3.right 覆盖，节点 4 及其子树就永远找不回来了。链：1 → 2 → 3。

第 4 次：cur = 4 非空，内层把 4 压栈（4 没有左孩子），弹出 node = 4，cur = null。重连后链：1 → 2 → 3 → 4。

第 5 次：弹出 node = 5，cur = 5.right = 6。重连后链：1 → 2 → 3 → 4 → 5。原来的根 5 落在了链的中间，这也说明返回值绝不能是 root。

第 6 次：cur = 6，内层压栈 6（无左孩子），弹出 node = 6，cur = 6.right = 8。链：… → 5 → 6。

第 7 次：cur = 8，压栈并弹出 node = 8，cur = null。链：1 → 2 → 3 → 4 → 5 → 6 → 8。

此时 cur 为空且栈空，循环退出，返回 dummy.right 即节点 1，正是完整的递增右链。

代码实现

class Solution {
    public TreeNode increasingBST(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        TreeNode dummy = new TreeNode(0);
        TreeNode tail = dummy;

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

            node.left = null;
            tail.right = node;
            tail = node;
        }
        return dummy.right;
    }
}

func increasingBST(root *TreeNode) *TreeNode {
    var stack []*TreeNode
    cur := root
    dummy := &TreeNode{}
    tail := dummy

    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]

        next := node.Right

        node.Left = nil
        tail.Right = node
        tail = node

        cur = next
    }
    return dummy.Right
}

复杂度分析

时间复杂度：$O(n)$。每个节点恰好入栈一次、出栈一次，出栈后只做常数次指针赋值，没有任何重复访问。

空间复杂度：$O(h)$，$h$ 为树高，来自显式栈中同时存在的节点数（一条左链的长度）。BST 退化成左链时 $h = n$，平衡时 $h = \log n$；哨兵与 tail 只占常数。

关键点总结

BST 的中序遍历天然升序，凡是要求「按大小顺序输出/重排 BST」的题，第一反应就是中序遍历，不需要额外排序。

原地重排指针的铁律是「读在写之前」：cur = node.right 必须先于任何对 node 的改写，否则未遍历的子树会随着指针覆盖一起丢失。

哨兵节点把「链为空时的首次挂接」和「后续挂接」统一成同一行代码，是链表构造类题目的通用减负手段。

node.left = null 之所以安全，是因为中序保证访问该节点时它的左子树已经处理完毕——顺序正确性是置空操作的前提，不能挪到别处。

返回 dummy.right 而不是 root：原树的根在中序序列里通常不在首位，本题的返回值是最小节点。

面试视角：递归中序 + 全局 tail 也能写，但迭代版更能展示对遍历顺序与指针时序的掌控；被追问空间时要能说清 $O(h)$ 的来源以及退化成链时为什么是 $O(n)$。

易错点总结

先重连再取 node.right：[5,3,6,2,4,null,8,1] 中处理节点 3 时，tail.right = node 之后 3.right 已被下一轮覆盖，节点 4 及其子树全部丢失，输出只剩 1 → 2 → 3。

忘记 node.left = null：[2,1] 会返回 1 → 2，但节点 2 的左指针仍指向 1，形成 1 → 2 → 1 的环，判题时遍历死循环。

tail = node 写在 tail.right = node 之前：tail 先指向新节点后再执行 tail.right = node，等于 node.right = node，第一个节点就自环。

返回 dummy 而不是 dummy.right：结果多出一个值为 0 的头节点，[1] 会输出 0 → 1。

返回 root：[5,3,6,2,4,null,8,1] 的根 5 在中序里排第五，返回它只能得到 5 → 6 → 8。

外层循环条件只写 cur != null：处理完最左节点后 cur 变为空，循环立刻退出，栈里剩下的祖先节点全部丢失，[2,1] 只输出 1。

外层循环条件只写 !stack.isEmpty()：初始栈为空，一次都不进循环，直接返回空。

内层压栈时压的是 cur.left 而不是 cur：最左节点永远不会入栈，[2,1] 会漏掉节点 1。

用递归中序但把 tail 声明为方法内局部变量：递归各层各持一份副本，链接断裂，[3,1,4] 只会留下最后一个节点；必须用成员变量或包装对象传递。

新建节点而不是重连指针：题目虽不禁止，但会额外占 $O(n)$ 空间，且面试中「能否原地」几乎是必问的追问，直接失去展示指针功力的机会。

误以为要把树重排成左链（值递减）：题目要求最小值在头、只保留右孩子；写反方向会让 [1,null,2] 输出 2 → 1。

相似题目

题目	难度	考察点
LCR 052. 递增顺序搜索树	简单	与本题同题，可直接套用
面试题 17.12. BiNode	简单	与本题同题，只是节点结构叫法不同
114. 二叉树展开为链表	中等	按先序展开而非中序，可用 Morris 思路做到 $O(1)$ 空间
426. 将二叉搜索树转化为排序的双向链表	中等	要同时维护前驱与后继两个方向，并把首尾接成循环
剑指 Offer 36. 二叉搜索树与双向链表	中等	与 426 同题
173. 二叉搜索树迭代器	中等	把中序遍历拆成可暂停的 `next()`，栈的状态要在调用之间保持
230. 二叉搜索树中第 K 小的元素	中等	中序走到第 k 个即可提前返回，考的是「不必遍历完」的剪枝
98. 验证二叉搜索树	中等	用中序序列是否严格递增来判定，只需记住前驱值而不改指针
538. 把二叉搜索树转换为累加树	中等	反向中序（右-根-左）累加后缀和，遍历方向与本题相反
1038. 从二叉搜索树到更大和树	中等	与 538 同题