1008. 前序遍历构造二叉搜索树【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 递归 + 上下界约束

1. 📝 题目描述

• leetcode

给定一个整数数组，它表示 BST(即 二叉搜索树 )的 先序遍历，构造树并返回其根。

保证 对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。

二叉搜索树 是一棵二叉树，其中每个节点， Node.left 的任何后代的值 严格小于 Node.val , Node.right 的任何后代的值 严格大于 Node.val。

二叉树的 前序遍历 首先显示节点的值，然后遍历Node.left，最后遍历Node.right。

---

示例 1：

输入：preorder = [8,5,1,7,10,12]
输出：[8,5,10,1,7,null,12]

示例 2：

输入: preorder = [1,3]
输出: [1,null,3]

---

提示：

• 1 <= preorder.length <= 100
• 1 <= preorder[i] <= 10^8
• preorder 中的值 互不相同

2. 🎯 s.1 - 递归 + 上下界约束

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number[]} preorder
 * @return {TreeNode}
 */
var bstFromPreorder = function (preorder) {
  let idx = 0
  const build = (lower, upper) => {
    if (idx === preorder.length) return null
    const val = preorder[idx]
    if (val < lower || val > upper) return null
    idx++
    const node = new TreeNode(val)
    node.left = build(lower, val)
    node.right = build(val, upper)
    return node
  }
  return build(-Infinity, Infinity)
}

• 时间复杂度：$O(n)$，其中 $n$ 是前序遍历数组的长度
• 空间复杂度：$O(n)$，递归调用栈的深度

算法思路：

• 利用 BST 的性质，维护当前节点值的上下界 [lower, upper]
• 如果当前值不在范围内，则返回 null
• 否则创建节点，递归构建左子树（上界为当前值）和右子树（下界为当前值）