- 正确答案：给定一个先序遍历序列（即根-左-右顺序），可以唯一重建一棵二叉搜索树（BST），时间复杂度可优化至 O(n)，空间复杂度 O(h)，其中 h 为树高（最坏 O(n)）。核心思路是利用 BST 的性质（左子树所有节点值 < 根 < 右子树所有节点值）和先序遍历“根最先出现”的特性，通过递归/迭代+单调栈/区间限界方式构造。最优解法为「递归区间限界法」或「单调栈法」，二者均可达到 O(n) 时间。 - 解答思路： 1. 先序序列第一个元素必为整棵树的根； 2. 由于 BST 性质，其右子树起始位置是序列中第一个大于根的元素位置； 3. 若暴力扫描找右子树起点，每层都 O(n)，总复杂度退化为 O(n²)（如退化链状树时）； 4. 优化关键：避免重复扫描 —— 使用「上下界递归」或「单调栈维护待扩展父节点」； 5. 「上下界递归法」：每个递归调用负责构建以当前值为根、且满足 min_val < node.val < max_val 的子树；先取当前值为根，若下一个值在 (min_val, root.val) 内，则递归构建左子树；若在 (root.val, max_val) 内，则回溯并构建右子树；用全局索引指针 i 遍历序列一次； 6. 「单调栈法」：模拟先序建树过程，栈中保存“可能还有右孩子待挂载”的节点（按值递减顺序），每次新节点 x，弹出栈顶所有 < x 的节点，最后一个被弹出的是 x 的父节点（且 x 是其右孩子）；若栈非空且栈顶 > x，则 x 是栈顶的左孩子。该方法显式建树，一次遍历，O(n) 时间，O(h) 空间。 - 深度知识讲解：【底层原理】BST 的先序序列具有“分段有序”结构：根 + （左子树先序） + （右子树先序），而左子树先序全部 < 根，右子树先序全部 > 根。但仅靠大小关系无法直接切分左右子树长度 —— 因为右子树可能紧邻根后立即开始（如 [5,3,1,4,8,6,9] 中，5 是根，3 开始左子树，8 是第一个 >5 的数，即右子树起点）。因此本质问题是：如何在 O(1) 均摊时间内定位每个子树的右边界？【上下界递归法的数学本质】将建树过程视为对先序序列的一次状态机驱动解析。每个节点的取值必须落在其祖先所施加的“值域约束”内：对于任意节点，其左子树受上界约束（不能 ≥ 父），右子树受下界约束（不能 ≤ 父）。递归函数 build(min_val, max_val) 表示“从当前序列位置开始，构造一颗所有节点 ∈ (min_val, max_val) 的 BST 子树”，返回构造后的子树根及消耗的序列长度（通过引用/全局索引实现）。该方法消除了显式查找分割点的需要，将决策逻辑内嵌于比较判断中，实现严格 O(n) 时间 —— 因为每个元素仅被访问一次（i 自增不回退）。【单调栈法的数据结构本质】栈在此处扮演“未闭合的左路径”角色：先序遍历中，我们始终走在最左路径上（不断向左下降），直到遇到一个比栈顶大的值，说明必须“向上回溯并转向右”。栈中元素构成一条从根出发的严格递减路径（即当前最左路径上的节点），新节点 x 若大于栈顶，则栈顶不可能是 x 的父（否则违反 BST），必须持续弹出，直到找到第一个 > x 的节点（即 x 的父），此时 x 成为其右孩子；若弹空，则 x 成为此前最后弹出节点的右孩子（即整棵树的新根？不，此时应有初始根，故实际不会弹空 —— 需预设哨兵或首节点入栈）。该栈行为等价于在笛卡尔树（Cartesian Tree）中按先序构造：BST + 先序 ≡ 笛卡尔树（以索引为堆序，值为BST序），而单调栈正是线性构造笛卡尔树的标准方法。【复杂度证明】 - 上下界递归：i 全局移动，每次调用至少消耗一个元素（创建一个节点），共 n 节点 → 最多 n 次函数调用，每次 O(1) 判断 → 总时间 O(n)；递归深度 = 树高 h → 空间 O(h)。 - 单调栈：每个元素最多入栈、出栈各一次 → 总操作 2n → 时间 O(n)；栈深 ≤ h → 空间 O(h)。 - 对比暴力法（每次递归扫描找右子树起点）：最坏 case（如先序为升序 [1,2,3,...,n]），第 i 层扫描 n−i 个元素 → ∑(n−i) = O(n²)。【稳定性与边界】两种方法均要求输入先序序列合法（即存在对应 BST）。若输入非法（如 [5,3,8,1] —— 1 出现在 8 后但 1<5，本应属左子树却错位），上下界法会在比较时自然失败（1 不满足 left 子树的 (−∞,5) 但已用完左机会，进入右分支时 1<5 导致违反 max_val=5，直接不创建）；单调栈法会建出结构但违反 BST 性质（需额外校验）。 - 代码示例（上下界递归法，Python 风格伪代码，O(n) 时间）： ``` class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def bst_from_preorder(preorder): if not preorder: return None i = 0 # 全局索引，使用 nonlocal 或类成员模拟 def build(min_val, max_val): nonlocal i if i >= len(preorder): return None val = preorder[i] if val < min_val or val > max_val: return None # 当前值越界，不消费，由父决定 node = TreeNode(val) i += 1 # 消费当前值 node.left = build(min_val, val) # 左子树：值 ∈ (min_val, val) node.right = build(val, max_val) # 右子树：值 ∈ (val, max_val) return node return build(float('-inf'), float('inf')) ``` - 代码示例（单调栈法，显式栈，O(n) 时间）： ``` def bst_from_preorder(preorder): if not preorder: return None root = TreeNode(preorder[0]) stack = [root] for i in range(1, len(preorder)): x = preorder[i] node = TreeNode(x) if x < stack[-1].val: # 当前值小，挂在栈顶左孩子 stack[-1].left = node else: # 弹出所有小于 x 的节点，最后一个弹出的是其父 parent = None while stack and stack[-1].val < x: parent = stack.pop() parent.right = node stack.append(node) return root ``` - 扩展知识： 1. 此问题与“从先序+后序构建BST”不同：后者不唯一（无中序无法区分左右），而先序+BST性质可唯一确定。 2. 类似问题：LeetCode 1008. Construct Binary Search Tree from Preorder Traversal（官方标答即上述两种 O(n) 解法）。 3. 工程意义：序列化/反序列化 BST 时，若只存先序（而非先序+中序），可节省 50% 空间，且 O(n) 反序列化高效。 4. 进阶：若输入含重复值，BST 定义需明确（通常 left ≤ root < right 或 left < root ≤ right），此时先序不再唯一确定树，需额外约定（如重复值全放右子树），上下界法需调整为闭区间。 5. 底层关联：单调栈法与“下一个更大元素”（NGE）问题同源；上下界递归与 LL(1) 语法分析中的递归下降解析器结构一致（每个非终结符对应一个带参数的 parse 函数）。

美团实习大模型应用算法一面

全站热榜

创作者周榜