1008. 前序遍历构造二叉搜索树
题目描述
输入一个整数数组 preorder，它是某棵二叉搜索树的前序遍历结果（先访问根，再访问左子树，最后访问右子树）。
这里的二叉搜索树要求：每个节点左子树中的所有值都严格小于该节点，右子树中的所有值都严格大于该节点。
根据 preorder 还原这棵树并返回根节点。输出时树用层序数组表示，null 表示空位。题目保证这样的树一定存在。
示例 1
输入：preorder = [8,5,1,7,10,12] 输出：[8,5,10,1,7,null,12]
解释：8 是根，5、1、7 都比 8 小，构成左子树；10、12 构成右子树。
示例 2
输入：preorder = [1,3] 输出：[1,null,3]
解释：3 比 1 大，只能是 1 的右孩子。
数据范围
1 <= preorder.length <= 1001 <= preorder[i] <= 10^8preorder中的值两两不同。
解题思路：递归 + 上界
前序的顺序是“根、左子树、右子树”。用一个全局下标 i 顺序消费数组，递归函数 build(bound) 只接受不超过 bound 的值。左子树的上界是当前节点值，右子树继承父级上界。遇到超界的值就返回 None，把它留给更高层的右子树。
为什么正确
build(bound) 被调用时，preorder[i:] 中开头连续不超过 bound 的那一段，正好是这棵子树的前序。
复杂度分析
时间 O(n)，每个值只被消费一次；递归栈 O(h)。
易错点
右子树的上界要继承父级的 bound，不是无穷大。否则 7 之后的 10 会被错误地挂到 5 的右侧。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
self.i = 0
def build(bound):
if self.i == len(preorder) or preorder[self.i] > bound:
return None
root = TreeNode(preorder[self.i])
self.i += 1
root.left = build(root.val)
root.right = build(bound)
return root
return build(math.inf)class Solution {
int i = 0;
public TreeNode bstFromPreorder(int[] preorder) {
i = 0;
return build(preorder, Integer.MAX_VALUE);
}
TreeNode build(int[] preorder, int bound) {
if (i == preorder.length || preorder[i] > bound) {
return null;
}
TreeNode root = new TreeNode(preorder[i]);
i++;
root.left = build(preorder, root.val);
root.right = build(preorder, bound);
return root;
}
}class Solution {
public:
int i = 0;
TreeNode* bstFromPreorder(vector<int>& preorder) {
i = 0;
return build(preorder, INT_MAX);
}
TreeNode* build(vector<int>& preorder, int bound) {
if (i == (int)preorder.size() || preorder[i] > bound) {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[i]);
i++;
root->left = build(preorder, root->val);
root->right = build(preorder, bound);
return root;
}
};func bstFromPreorder(preorder []int) *TreeNode {
i := 0
var build func(bound int) *TreeNode
build = func(bound int) *TreeNode {
if i == len(preorder) || preorder[i] > bound {
return nil
}
root := &TreeNode{Val: preorder[i]}
i++
root.Left = build(root.Val)
root.Right = build(bound)
return root
}
return build(math.MaxInt32)
}var bstFromPreorder = function(preorder) {
let i = 0;
const build = (bound) => {
if (i === preorder.length || preorder[i] > bound) {
return null;
}
const root = new TreeNode(preorder[i]);
i++;
root.left = build(root.val);
root.right = build(bound);
return root;
};
return build(Infinity);
};function bstFromPreorder(preorder: number[]): TreeNode | null {
let i = 0;
const build = (bound: number): TreeNode | null => {
if (i === preorder.length || preorder[i] > bound) {
return null;
}
const root = new TreeNode(preorder[i]);
i++;
root.left = build(root.val);
root.right = build(bound);
return root;
};
return build(Infinity);
}其他解法
两种方法都是线性时间。递归法用上界参数直接表达 BST 的值域约束，代码最短；单调栈法用显式栈模拟同样的过程，避免了深递归。
解法 2：单调栈 时间 O(n)，空间 O(n)
先序遍历中，每个新值要么是栈顶节点的左孩子，要么是某个祖先的右孩子。用栈保存从根往下、还可能接收右孩子的节点，栈中值从底到顶递减。读到新值 v 时，不断弹出比 v 小的节点，最后弹出的那个就是 v 的父节点，v 作为其右孩子；若没有弹出任何节点，v 就是栈顶的左孩子。最后把新节点压栈。
迭代实现，没有递归深度的问题，展示了单调栈在树构造中的应用。父子关系的判断不如递归上界法直观。
class Solution:
def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
root = TreeNode(preorder[0])
stack = [root]
for v in preorder[1:]:
node = TreeNode(v)
parent = stack[-1]
while stack and stack[-1].val < v:
parent = stack.pop()
if parent.val < v:
parent.right = node
else:
parent.left = node
stack.append(node)
return rootclass Solution {
public TreeNode bstFromPreorder(int[] preorder) {
TreeNode root = new TreeNode(preorder[0]);
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
for (int k = 1; k < preorder.length; k++) {
int v = preorder[k];
TreeNode node = new TreeNode(v);
TreeNode parent = stack.peek();
while (!stack.isEmpty() && stack.peek().val < v) {
parent = stack.pop();
}
if (parent.val < v) parent.right = node;
else parent.left = node;
stack.push(node);
}
return root;
}
}class Solution {
public:
TreeNode* bstFromPreorder(vector<int>& preorder) {
TreeNode* root = new TreeNode(preorder[0]);
vector<TreeNode*> stk = {root};
for (int k = 1; k < (int)preorder.size(); k++) {
int v = preorder[k];
TreeNode* node = new TreeNode(v);
TreeNode* parent = stk.back();
while (!stk.empty() && stk.back()->val < v) {
parent = stk.back();
stk.pop_back();
}
if (parent->val < v) parent->right = node;
else parent->left = node;
stk.push_back(node);
}
return root;
}
};func bstFromPreorder(preorder []int) *TreeNode {
root := &TreeNode{Val: preorder[0]}
stack := []*TreeNode{root}
for _, v := range preorder[1:] {
node := &TreeNode{Val: v}
parent := stack[len(stack)-1]
for len(stack) > 0 && stack[len(stack)-1].Val < v {
parent = stack[len(stack)-1]
stack = stack[:len(stack)-1]
}
if parent.Val < v {
parent.Right = node
} else {
parent.Left = node
}
stack = append(stack, node)
}
return root
}var bstFromPreorder = function(preorder) {
const root = new TreeNode(preorder[0]);
const stack = [root];
for (let k = 1; k < preorder.length; k++) {
const v = preorder[k];
const node = new TreeNode(v);
let parent = stack[stack.length - 1];
while (stack.length && stack[stack.length - 1].val < v) {
parent = stack.pop();
}
if (parent.val < v) parent.right = node;
else parent.left = node;
stack.push(node);
}
return root;
};function bstFromPreorder(preorder: number[]): TreeNode | null {
const root = new TreeNode(preorder[0]);
const stack: TreeNode[] = [root];
for (let k = 1; k < preorder.length; k++) {
const v = preorder[k];
const node = new TreeNode(v);
let parent = stack[stack.length - 1];
while (stack.length && stack[stack.length - 1].val < v) {
parent = stack.pop()!;
}
if (parent.val < v) parent.right = node;
else parent.left = node;
stack.push(node);
}
return root;
}