LeetCode 1008. 前序遍历构造二叉搜索树

Categories:

题目描述
思路分析
1. 解法一：递归 + 上界（推荐）
相似题目

题目描述

✅ 1008. 前序遍历构造二叉搜索树

思路分析

解法一：递归 + 上界（推荐）

核心思路：

前序序列中，根节点在最前，左子树值都小于根，右子树值都大于根。

使用全局索引按序读取，递归构建子树并传入上界限制。

当前值超过上界时停止构建，回溯到上层。

复杂度分析：

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

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

class Solution {
    private int idx = 0;

    public TreeNode bstFromPreorder(int[] preorder) {
        return build(preorder, Integer.MAX_VALUE);
    }

    private TreeNode build(int[] preorder, int bound) {
        if (idx == preorder.length || preorder[idx] > bound) {
            return null;
        }

        int val = preorder[idx++];
        TreeNode node = new TreeNode(val);

        node.left = build(preorder, val);
        node.right = build(preorder, bound);

        return node;
    }
}

func bstFromPreorder(preorder []int) *TreeNode {
	idx := 0
	return build(preorder, &idx, 1<<31-1)
}

func build(preorder []int, idx *int, bound int) *TreeNode {
	if *idx == len(preorder) || preorder[*idx] > bound {
		return nil
	}

	val := preorder[*idx]
	*idx += 1

	node := &TreeNode{Val: val}
	node.Left = build(preorder, idx, val)
	node.Right = build(preorder, idx, bound)

	return node
}

相似题目

题目	难度	考察点
1008. 前序遍历构造二叉搜索树	中等	BST、递归
108. 将有序数组转换为二叉搜索树	简单	BST
701. 二叉搜索树中的插入操作	中等	BST
889. 根据前序和后序遍历构造二叉树	中等	树构建
105. 从前序与中序遍历序列构造二叉树	中等	递归

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/49875407