LeetCode LCR 052. 递增顺序搜索树

Categories:

题目描述
思路分析
1. 解法一：中序遍历重连（推荐）
相似题目

题目描述

✅ LCR 052. 递增顺序搜索树

思路分析

解法一：中序遍历重连（推荐）

核心思路：

二叉搜索树中序遍历为升序序列。

用虚拟头结点 dummy，遍历到的每个节点都连接为 prev.right，并将其 left 置空。

最终 dummy.right 即为递增顺序树。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数。

空间复杂度：O(h)，其中 h 表示树高，递归栈占用。

class Solution {
    private TreeNode prev;

    public TreeNode increasingBST(TreeNode root) {
        TreeNode dummy = new TreeNode(0);
        prev = dummy;

        inorder(root);
        return dummy.right;
    }

    private void inorder(TreeNode node) {
        if (node == null) {
            return;
        }

        inorder(node.left);

        // 断开左指针并接到结果链上
        node.left = null;
        prev.right = node;
        prev = node;

        inorder(node.right);
    }
}

func increasingBST(root *TreeNode) *TreeNode {
    dummy := &TreeNode{}
    prev := dummy

    var inorder func(node *TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }

        inorder(node.Left)

        // 断开左指针并接到结果链上
        node.Left = nil
        prev.Right = node
        prev = node

        inorder(node.Right)
    }

    inorder(root)
    return dummy.Right
}

相似题目

题目	难度	考察点
230. 二叉搜索树中第 K 小的元素	中等	中序遍历
98. 验证二叉搜索树	中等	中序遍历
538. 把二叉搜索树转换为累加树	中等	反向中序
530. 二叉搜索树的最小绝对差	简单	中序遍历
173. 二叉搜索树迭代器	中等	栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/16273188