LeetCode LCR 052. 递增顺序搜索树

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

题目描述

✅ LCR 052. 递增顺序搜索树

image-20260929005931356

image-20260929005931363

题意分析

把二叉搜索树按中序顺序重排成一条右链：最左节点成为新根，每个节点的左孩子为空，右孩子指向下一个节点。BST 的中序序列已经有序，因此按访问顺序串接即可，无需重新排序。

解法：迭代中序原地串接

核心思路

[!blue]

用显式栈进行中序遍历：从 cur 一路向左压栈，走到空后弹出一个节点，此时它的左子树已经处理完，可以访问它；随后转到它的右子树，重复同样过程。

head 保存结果头，tail 保存最后一个已接入的节点。第一次弹出的节点是中序首项，令它成为 head；以后每弹出一个节点，就令 tail.right 指向它，再更新 tail。这样所有已处理节点始终按中序顺序连接。

访问当前节点后将它的左指针清空，因为那棵左子树已经遍历并接入结果，不再依赖这个旧连接。当前节点原来的右指针仍然保留，立即用 cur=cur.right 进入未处理的右子树；等下一次串接改写旧尾节点的右指针时，遍历已经通过 cur 或栈保存了所需引用，不会丢失节点。

每个节点恰好弹栈一次，也就恰好接入结果一次。最后一个节点是最右节点，其原右孩子本来就为空，所以遍历结束时得到一条完整的有序右链。

解题步骤

  • 初始化空栈、空的 head 与 tail，令 cur=root。
  • 当 cur 非空或栈非空时，先把当前子树的左链全部压栈。
  • 弹出节点：首次访问时设置头节点，否则接到 tail.right。
  • 更新尾节点，清空当前节点的左指针，再转向其原右子树。
  • 当前节点和栈都为空时返回 head。

循环必须同时检查当前节点和栈：前者表示刚进入的子树，后者保存尚待访问的祖先。单节点树、纯左链和纯右链都按同样的中序规则处理；整个过程复用原节点，会修改原树结构。

代码实现

class Solution {
    public TreeNode increasingBST(TreeNode root) {
        TreeNode head = null;
        TreeNode 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$ 为树高；不创建新的树节点。

关键点总结

[!green]

  • 中序顺序决定新链顺序，head 和 tail 分别负责保留结果入口和追加节点。
  • 左子树处理完后才能清空左指针，原右子树则要先交给遍历继续处理。
  • 原地重连复用节点，但仍需要栈保存尚未访问的祖先。

易错点总结

[!yellow]

  • 按中序顺序接入节点，并把每个节点的 left 清空。
  • 保留独立的 head 与 tail，移动尾指针时不能丢失结果头。
  • 循环同时考虑当前节点与待处理栈；弹出节点后还要遍历其原右子树。

相似题目

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