前序遍历构造二叉搜索树 图解题解

这道题到底在问什么

输入

preorder = 10,5,3,7,15,12,18

输出

BST 层序 10,5,15,3,7,12,18

输入

preorder = 4,5

输出

4 的右孩子是 5

最优解：一步一步想明白

1. 3记住「取首元素当根;下一个值 ≤ bound 就往当前子树挂、> bound 就回退给祖先;左子树上界收成根值、右子树上界沿用父界」,下面逐帧套它。
2. 4上界 +∞轮到根,上界是 +∞。下一个待读值 10 满足 10 ≤ +∞,说明它属于这棵子树,就在这儿建节点 10。
3. 5读到第 1 个建好节点 10(紫色),读取指针前进一格。接着递归两边:左孩子的上界收紧成 10(左子树都要比 10 小),右孩子的上界沿用父亲传来的 +∞。
4. 6上界 10轮到节点 10 的左孩子,上界是 10。下一个待读值 5 满足 5 ≤ 10,说明它属于这棵子树,就在这儿建节点 5。
5. 7读到第 2 个建好节点 5(紫色),读取指针前进一格。接着递归两边:左孩子的上界收紧成 5(左子树都要比 5 小),右孩子的上界沿用父亲传来的 10。
6. 8上界 5轮到节点 5 的左孩子,上界是 5。下一个待读值 3 满足 3 ≤ 5,说明它属于这棵子树,就在这儿建节点 3。
7. 9读到第 3 个建好节点 3(紫色),读取指针前进一格。接着递归两边:左孩子的上界收紧成 3(左子树都要比 3 小),右孩子的上界沿用父亲传来的 5。
8. 10超过上界轮到节点 3 的左孩子,它的上界是 3。下一个待读值 7 已经 7 > 3,超过上界,说明它不属于这里,这个位置判为空、不取值,交回给上一层去接。
9. 11超过上界轮到节点 3 的右孩子,它的上界是 5。下一个待读值 7 已经 7 > 5,超过上界,说明它不属于这里,这个位置判为空、不取值,交回给上一层去接。
10. 12上界 10轮到节点 5 的右孩子,上界是 10。下一个待读值 7 满足 7 ≤ 10,说明它属于这棵子树,就在这儿建节点 7。
11. 13读到第 4 个建好节点 7(紫色),读取指针前进一格。接着递归两边:左孩子的上界收紧成 7(左子树都要比 7 小),右孩子的上界沿用父亲传来的 10。
12. 14超过上界轮到节点 7 的左孩子,它的上界是 7。下一个待读值 15 已经 15 > 7,超过上界,说明它不属于这里,这个位置判为空、不取值,交回给上一层去接。
13. 15超过上界轮到节点 7 的右孩子,它的上界是 10。下一个待读值 15 已经 15 > 10,超过上界,说明它不属于这里,这个位置判为空、不取值,交回给上一层去接。
14. 16上界 +∞轮到节点 10 的右孩子,上界是 +∞。下一个待读值 15 满足 15 ≤ +∞,说明它属于这棵子树,就在这儿建节点 15。
15. 17读到第 5 个建好节点 15(紫色),读取指针前进一格。接着递归两边:左孩子的上界收紧成 15(左子树都要比 15 小),右孩子的上界沿用父亲传来的 +∞。
16. 18上界 15轮到节点 15 的左孩子,上界是 15。下一个待读值 12 满足 12 ≤ 15,说明它属于这棵子树,就在这儿建节点 12。
17. 19读到第 6 个建好节点 12(紫色),读取指针前进一格。接着递归两边:左孩子的上界收紧成 12(左子树都要比 12 小),右孩子的上界沿用父亲传来的 15。
18. 20超过上界轮到节点 12 的左孩子,它的上界是 12。下一个待读值 18 已经 18 > 12,超过上界,说明它不属于这里,这个位置判为空、不取值,交回给上一层去接。
19. 21超过上界轮到节点 12 的右孩子,它的上界是 15。下一个待读值 18 已经 18 > 15,超过上界,说明它不属于这里,这个位置判为空、不取值,交回给上一层去接。
20. 22上界 +∞轮到节点 15 的右孩子,上界是 +∞。下一个待读值 18 满足 18 ≤ +∞,说明它属于这棵子树,就在这儿建节点 18。
21. 23读到第 7 个建好节点 18(紫色),读取指针前进一格。接着递归两边:左孩子的上界收紧成 18(左子树都要比 18 小),右孩子的上界沿用父亲传来的 +∞。
22. 24已读完轮到节点 18 的左孩子,但前序串已经全部读完、没有值可取了,这个位置判为空,回到上一层。
23. 25已读完轮到节点 18 的右孩子,但前序串已经全部读完、没有值可取了,这个位置判为空,回到上一层。
24. 26原样重建前序串读完,整棵 BST 重建好了:根 10,左 5(挂 3、7)、右 15(挂 12、18)。验证它的中序是 3,5,7,10,12,15,18,严格升序,确实是合法 BST。回头看,每个值只被取用一次、靠一个上界就分到了该去的位置,一遍 O(n) 搞定。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List, Optional
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
        i = 0
        def build(bound):
            nonlocal i
            if i == len(preorder) or preorder[i] > bound: return None
            root = TreeNode(preorder[i]); i += 1
            root.left = build(root.val)
            root.right = build(bound)
            return root
        return build(float('inf'))

#include <algorithm>
#include <climits>
#include <functional>
#include <iterator>
#include <numeric>
#include <vector>
using namespace std;
struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode():val(0),left(nullptr),right(nullptr){} TreeNode(int x):val(x),left(nullptr),right(nullptr){} TreeNode(int x,TreeNode*l,TreeNode*r):val(x),left(l),right(r){}};
class Solution{ int i=0; public: TreeNode* bstFromPreorder(vector<int>& preorder){ i=0; return build(preorder,INT_MAX);} TreeNode* build(vector<int>& a,int bound){ if(i==(int)a.size()||a[i]>bound)return nullptr; TreeNode* r=new TreeNode(a[i++]); r->left=build(a,r->val); r->right=build(a,bound); return r;} };

import java.util.*;
class TreeNode{int val;TreeNode left,right;TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val,TreeNode left,TreeNode right){this.val=val;this.left=left;this.right=right;}}
class Solution{ int i; public TreeNode bstFromPreorder(int[] preorder){ i=0; return build(preorder,Integer.MAX_VALUE);} TreeNode build(int[] a,int bound){ if(i==a.length||a[i]>bound)return null; TreeNode r=new TreeNode(a[i++]); r.left=build(a,r.val); r.right=build(a,bound); return r;} }

复杂度

面试官可能追问