LeetCode LCR 052. 递增顺序搜索树

约 8 分钟
文章信息 5 个分类 6 个标签
分类
LeetCode 简单 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
深度优先搜索 树 二叉树 LCR 栈 二叉搜索树
目录

题目描述

✅ LCR 052. 递增顺序搜索树

题意分析

题目目标：把一棵二叉搜索树重排成一条"只有右孩子"的链：最小的节点作为新的根，此后每个节点的左孩子为空、右孩子是比它大的下一个节点，返回新链的头。
核心约束：结果要求节点值从头到尾递增，而二叉搜索树的中序序列恰好就是升序，这说明整个任务等价于"按中序访问节点并依次串起来"，不需要任何排序也不需要比较值的大小。
边界处理：树可能只有一个节点，此时它自己就是答案；原树可能是一条纯左链或纯右链；每个被串上的节点都必须把左指针清空，否则结果里会残留旧结构；节点值可能重复出现在题目变种中，但不影响串接逻辑。
实现取舍：可以新建节点复制值，也可以直接改写原有节点的指针。后者不额外分配内存，但必须小心——改写指针的同时还要靠原指针继续遍历，顺序稍有差池就会丢失尚未访问的子树。

解法：深度优先搜索

核心思路

最省事的做法是先做一次中序遍历把所有节点值收集进数组，再按数组新建一条右链。这样两趟走完，正确且好写，但额外花掉 $O(n)$ 的数组空间，还创建了 n 个新节点。
观察到中序遍历本身就是按升序逐个"吐出"节点的过程：只要在吐出的瞬间就把它接到已建好链条的尾部，一趟遍历就能边遍历边成型，不需要中间数组。
由此确定不变量：每次从中序序列取出一个节点时，head 指向已建好链条的头、tail 指向它的尾，且链条上的节点恰好是中序序列中已经处理过的那些，顺序升序。新节点到来时若 head 为空说明它是最小的那个，直接充当头；否则挂到 tail.right 上；无论哪种情况，tail 都随即更新为新节点。
遍历采用显式栈的写法：cur 一路向左把沿途节点压栈，直到走到空；弹栈得到的就是当前最小的未访问节点，处理它，然后转向它的右子树继续。之所以选迭代而非递归，是因为改写指针的时机在这里更容易看清——处理节点时必须先把 cur.right 读出来交给遍历，再把它的左指针清空，两个操作都只碰当前节点，不会影响栈里待访问的祖先。

解题步骤

  • 准备 head、tail 两个指针以及一个栈，cur 初始指向根。为什么需要两个指针：head 是最终要返回的结果，tail 是每次串接的锚点，二者职责不同不能合并。
  • 外层循环条件是"栈非空或 cur 非空"。为什么两个条件缺一不可：栈空但 cur 非空发生在刚转入某棵右子树时，cur 空但栈非空发生在某条左链走到底时，只写其中一个都会提前结束遍历。
  • 内层 while (cur != null) 把 cur 及其左链全部压栈。为什么一路向左：中序要求先访问最左端，压栈顺序保证了弹出时从最小值开始。
  • 弹栈得到当前节点后，若 head 为空则令 head = cur，否则 tail.right = cur。为什么用 head 是否为空来区分：第一个被中序访问到的节点就是整棵树的最小值，它没有前驱可挂，只能当头。
  • 更新 tail = cur，再执行 cur.left = null。为什么必须清空左指针：题目要求结果链上每个节点都没有左孩子；而且此时该节点的左子树已经全部被中序访问完毕，断开不会丢失任何信息。
  • 最后 cur = cur.right 转向右子树。为什么这一步安全：虽然稍后这个节点的 right 会被下一次串接覆盖，但覆盖发生时 cur 早已把原来的右孩子读走了，遍历不会丢失分支。
  • 以 具体用例：树 [5, 3, 6, 2, 4, null, 8]（根 5；左子树 3 的孩子是 2、4；右子树 6 的右孩子是 8）走一遍。cur 从 5 一路向左压入 5、3、2，cur 变空。弹出 2：head 为空故 head = 2，tail = 2，清空 2 的左指针，cur = 2.right = null。弹出 3：tail.right = 3 即 2 -> 3，tail = 3，清空 3 的左指针，cur = 3.right = 4，压入 4。弹出 4：链变成 2 -> 3 -> 4，cur 转空。弹出 5：链变成 2 -> 3 -> 4 -> 5，注意此刻 5 的右指针原本指向 6，我们先读走它再让下一次串接覆盖，cur = 6，压入 6。弹出 6：链接到 ... -> 6，cur = 8，压入 8。弹出 8：链接到末尾。栈空且 cur 空，返回 head，最终链为 2 -> 3 -> 4 -> 5 -> 6 -> 8，全部节点的左指针为空。

代码实现

// 核心实现：深度优先搜索，维护必要状态并避免重复处理。
class Solution {
    public TreeNode increasingBST(TreeNode root) {
        TreeNode head = null, tail = null;
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            if (head == null) {
                head = cur;
            } else {
                tail.right = cur;
            }
            tail = cur;
            cur.left = null;
            cur = cur.right;
        }
        return head;
    }
}

// 核心实现：深度优先搜索，维护必要状态并避免重复处理。
func increasingBST(root *TreeNode) *TreeNode {
    var head, tail *TreeNode
    stack := make([]*TreeNode, 0)
    cur := root
    for len(stack) > 0 || cur != nil {
        for cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        }
        cur = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if head == nil {
            head = cur
        } else {
            tail.Right = cur
        }
        tail = cur
        cur.Left = nil
        cur = cur.Right
    }
    return head
}

复杂度分析

  • 时间复杂度：$O(n)$。凭什么：每个节点恰好入栈一次、出栈一次，出栈时只做常数次指针赋值，没有任何值比较或重复遍历。
  • 空间复杂度：$O(h)$，h 为树高，最坏（左链）为 $O(n)$。凭什么：只用了一个显式栈保存当前的左链祖先，没有创建任何新节点，也没有额外的数组。

关键点总结

  • 二叉搜索树的中序序列天然升序，凡是题面出现"递增""第 K 小""相邻差值"等字眼，第一反应就应该是中序遍历，而不是先想着排序或比较。
  • "边遍历边构造"可以省掉中间容器：只要在访问节点的瞬间就完成它在结果中的定位，一趟遍历即可成型，这个思路同样适用于把树拉平成链表。
  • 原地改写指针的安全前提是"先读后写"：任何还要用于继续遍历的指针，必须在被覆盖之前取走，这是所有链式重排题的通用纪律。
  • 中序访问一个节点时，它的左子树必然已经处理完毕，所以此刻断开左指针绝对安全——这条归纳性质是清空左指针那一行的全部依据。
  • 面试视角：面试官可能追问"能不能不用栈"。递归写法只需把 tail 提为成员变量并在中序位置做同样的串接，空间从显式栈变成调用栈；进一步的高阶答案是用 Morris 遍历把空间压到 $O(1)$。能给出迭代、递归、Morris 三层递进，并说明各自适用场景，这道简单题就答出了深度。

易错点总结

  • 错误写法：忘记 cur.left = null → 树 [2, 1] 的结果链上根节点 1 仍指向原来的左子树，判题遍历时发现左孩子非空直接判错。
  • 错误写法：先写 cur = cur.right 再写 cur.left = null 这类顺序调换尚可接受，但若把串接 tail.right = cur 放到读取 cur.right 之后 → 当前节点的右孩子已被覆盖成下一个节点，树 [5, 3, 6] 中 6 永远进不了遍历，结果缺失节点。
  • 错误写法：外层循环条件只写 !stack.isEmpty() → 树 [1, null, 2] 时根出栈后栈为空但 cur 指向 2，循环提前结束，返回的链只有一个节点。
  • 错误写法：外层循环条件只写 cur != null → 树 [2, 1] 中 cur 走到 1 的左空后立刻退出，一个节点都没串上，返回空。
  • 错误写法：用 head 之外的方式判断首节点，比如用一个计数器却在 continue 分支忘记自增 → 首节点被当成非首节点，对空的 tail 取 right 直接空指针异常。
  • 错误写法：把 tail 与 head 合并成一个指针 → 串接时移动了头指针，最终返回的是链尾 8 而不是链头 2。
  • 错误写法：改成前序或后序遍历串接 → 树 [5, 3, 6] 前序得到 5 -> 3 -> 6，值不递增，完全不满足题意。
  • 错误写法：新建节点复制值时忘记把新节点的左指针置空（某些语言默认值不为空）或忘记维护尾指针 → 结果链断裂，只返回单个节点。
  • 错误写法：递归写法里把 tail 声明为局部变量而不是成员变量或闭包变量 → 每层递归各持一份，串接结果互相覆盖，最终只剩最后一段。
  • 错误写法：先把节点值收集进数组再新建链，却沿用原节点对象且未清空左指针 → 旧的左子树被带进结果，形成环状或分叉结构，判题超时或报错。

相似题目

题目 难度 考察点
94. 二叉树的中序遍历 简单 中序迭代模板本身，只输出序列不改结构
173. 二叉搜索树迭代器 中等 把中序拆成可暂停的迭代器，考察栈状态的持久化
230. 二叉搜索树中第 K 小的元素 中等 中序过程中提前终止，考察计数与剪枝时机
783. 二叉搜索树节点最小距离 简单 需在中序中维护前驱值做差，而非重排结构
99. 恢复二叉搜索树 中等 借中序有序性定位两个逆序对，改的是节点值不是指针
426. 将二叉搜索树转化为排序的双向链表 中等 同样中序串接，但要双向指针且首尾相连