cswork / 模板打开 500 路题单

第 13 站 · 链表与树

二叉搜索树

迭代中序：按顺序走 BST 时间 O(h + k) · 空间 O(h)

周赛难度分 难度分 1335–难度分 1335· 中位 难度分 1335（1/15 道题有 zerotrac 周赛分）

打开 500 路题单 · 第 13 站 · 15 题
先学
学完去
没有后续站依赖它。
面试频次
7 家公司考过 · 面经出现 11 次Amazon 3、Meta 3、Microsoft 1、Pinduoduo 1、Salesforce 1

先做这道

LC 700二叉搜索树中的搜索简单
卡住再看

利用大小关系只搜索一个子树。

要点

  1. BST 的中序遍历是升序的：第 k 小、验证 BST、找前驱后继，都能转成中序问题。
  2. 验证 BST 要把上下界 (lo, hi) 往下传，每个结点都必须落在祖先给出的开区间里。
  3. 查找和插入只走一条路径，复杂度是 O(h)：平衡时 O(log n)，退化成链时 O(n)。

易错点

  • 只拿结点和它的左右孩子比较，发现不了「右子树深处有比根还小的值」。
  • 用 INT_MIN / INT_MAX 当边界，结点值恰好是极值时会误判；用 long 或空值表示「无界」。
  • 迭代中序里忘了转向 node.right，会重复弹出同一批结点或者提前结束。

看动画

一步一步播放这个模式在小例子上的执行过程。可以暂停、单步前进或后退，拖动进度条跳到任意一步。

交互演示 · 逐步观察

二叉搜索树 · 查找、插入、删除

依次执行 find(6)、insert(5)、delete(1)、delete(14)、delete(8)

换个输入
831647101413
当前处理已发现 / 已计算答案
操作
—
比较次数
0
中序
1 3 4 6 7 8 10 13 14

依次插入 8, 3, 10, 1, 6, 14, 4, 7, 13 得到这棵二叉搜索树：每个节点左边都比它小，右边都比它大，所以中序遍历是有序的。

始终成立任意节点：左子树的键都比它小，右子树的键都比它大。

模板

选一种语言展开。四种写法实现的是同一个模板，每一份都编译运行过，并用测试数据核对了输出。看完用它重写热身题 LC 700。

Python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right


def kth_smallest(root, k: int) -> int:
    """1-indexed; assumes 1 <= k <= number of nodes."""
    stack, node = [], root
    while True:
        while node:  # go as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()  # the next value in sorted order
        k -= 1
        if k == 0:
            return node.val
        node = node.right
C++
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v, TreeNode* l = nullptr, TreeNode* r = nullptr) : val(v), left(l), right(r) {}
};

// 1-indexed; assumes 1 <= k <= number of nodes.
int kthSmallest(TreeNode* root, int k) {
    stack<TreeNode*> st;
    TreeNode* node = root;
    while (true) {
        for (; node; node = node->left) st.push(node);  // go as far left as possible
        node = st.top();  // the next value in sorted order
        st.pop();
        if (--k == 0) return node->val;
        node = node->right;
    }
}
Java
class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    // 1-indexed; assumes 1 <= k <= number of nodes.
    int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> st = new ArrayDeque<>();
        TreeNode node = root;
        while (true) {
            for (; node != null; node = node.left) st.push(node); // go as far left as possible
            node = st.pop(); // the next value in sorted order
            if (--k == 0) return node.val;
            node = node.right;
        }
    }
}
Go
type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

// kthSmallest is 1-indexed and assumes 1 <= k <= number of nodes.
func kthSmallest(root *TreeNode, k int) int {
	var st []*TreeNode
	node := root
	for {
		for ; node != nil; node = node.Left { // go as far left as possible
			st = append(st, node)
		}
		node = st[len(st)-1] // the next value in sorted order
		st = st[:len(st)-1]
		k--
		if k == 0 {
			return node.Val
		}
		node = node.Right
	}
}

常见变体

这一站的题还会用到下面 2 种写法。展开看什么时候换用它，代码同样四种语言都跑过测试。

上下界递归：每个结点落在祖先给的开区间里时间 O(n) · 递归深度 O(h)

只和父结点比较不够（右子树深处的小值也违规）：递归时带着 (lo, hi) 开区间往下传，走左边把上界收成当前值，走右边把下界收成当前值。LC 98 验证二叉搜索树；用 long 或无穷大做初始边界，防止结点值等于 int 极值。

Python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def is_valid_bst(root) -> bool:
    """Every node lies strictly inside the bounds its ancestors set (LC 98)."""

    def ok(node, lo, hi) -> bool:  # node.val must be in the open range (lo, hi)
        if not node:
            return True
        if not lo < node.val < hi:
            return False
        return ok(node.left, lo, node.val) and ok(node.right, node.val, hi)

    return ok(root, float("-inf"), float("inf"))
C++
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v, TreeNode* l = nullptr, TreeNode* r = nullptr) : val(v), left(l), right(r) {}
};

// Every node lies strictly inside the bounds its ancestors set (LC 98).
bool isValidBst(TreeNode* root) {
    function<bool(TreeNode*, long long, long long)> ok = [&](TreeNode* node, long long lo, long long hi) {
        if (!node) return true;  // node->val must be in the open range (lo, hi)
        if (node->val <= lo || node->val >= hi) return false;
        return ok(node->left, lo, node->val) && ok(node->right, node->val, hi);
    };
    return ok(root, LLONG_MIN, LLONG_MAX);
}
Java
class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    // Every node lies strictly inside the bounds its ancestors set (LC 98).
    boolean isValidBst(TreeNode root) {
        return ok(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    // node.val must be in the open range (lo, hi).
    private boolean ok(TreeNode node, long lo, long hi) {
        if (node == null) return true;
        if (node.val <= lo || node.val >= hi) return false;
        return ok(node.left, lo, node.val) && ok(node.right, node.val, hi);
    }
}
Go
import "math"

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

// isValidBst reports whether every node lies strictly inside the bounds its ancestors set (LC 98).
func isValidBst(root *TreeNode) bool {
	var ok func(node *TreeNode, lo, hi int) bool // node.Val must be in the open range (lo, hi)
	ok = func(node *TreeNode, lo, hi int) bool {
		if node == nil {
			return true
		}
		if node.Val <= lo || node.Val >= hi {
			return false
		}
		return ok(node.Left, lo, node.Val) && ok(node.Right, node.Val, hi)
	}
	return ok(root, math.MinInt, math.MaxInt)
}
删除结点：两个孩子时换成中序后继时间 O(h) · 递归深度 O(h)

在 BST 里删除或修剪（LC 450 删除二叉搜索树中的节点、LC 669 修剪）：按大小往一边递归，返回新的子树根接回父结点；要删的结点最多一个孩子时直接把孩子提上来，两个孩子时把右子树最小值（中序后继）的值拷过来，再去右子树里删掉它。

Python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def delete_node(root, key: int):
    """The BST without key, if it was there (LC 450)."""
    if not root:
        return None
    if key < root.val:
        root.left = delete_node(root.left, key)
    elif key > root.val:
        root.right = delete_node(root.right, key)
    else:
        if not root.left or not root.right:  # zero or one child: lift it up
            return root.left or root.right
        succ = root.right  # two children: take the inorder successor's value...
        while succ.left:
            succ = succ.left
        root.val = succ.val
        root.right = delete_node(root.right, succ.val)  # ...and delete it below
    return root
C++
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v, TreeNode* l = nullptr, TreeNode* r = nullptr) : val(v), left(l), right(r) {}
};

// The BST without key, if it was there (LC 450).
TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return nullptr;
    if (key < root->val) root->left = deleteNode(root->left, key);
    else if (key > root->val) root->right = deleteNode(root->right, key);
    else {
        if (!root->left || !root->right) return root->left ? root->left : root->right;  // zero or one child: lift it up
        TreeNode* succ = root->right;  // two children: take the inorder successor's value...
        while (succ->left) succ = succ->left;
        root->val = succ->val;
        root->right = deleteNode(root->right, succ->val);  // ...and delete it below
    }
    return root;
}
Java
class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    // The BST without key, if it was there (LC 450).
    TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        if (key < root.val) root.left = deleteNode(root.left, key);
        else if (key > root.val) root.right = deleteNode(root.right, key);
        else {
            if (root.left == null || root.right == null) return root.left != null ? root.left : root.right; // lift the only child
            TreeNode succ = root.right; // two children: take the inorder successor's value...
            while (succ.left != null) succ = succ.left;
            root.val = succ.val;
            root.right = deleteNode(root.right, succ.val); // ...and delete it below
        }
        return root;
    }
}
Go
type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

// deleteNode returns the BST without key, if it was there (LC 450).
func deleteNode(root *TreeNode, key int) *TreeNode {
	if root == nil {
		return nil
	}
	switch {
	case key < root.Val:
		root.Left = deleteNode(root.Left, key)
	case key > root.Val:
		root.Right = deleteNode(root.Right, key)
	default:
		if root.Left == nil { // zero or one child: lift it up
			return root.Right
		}
		if root.Right == nil {
			return root.Left
		}
		succ := root.Right // two children: take the inorder successor's value...
		for succ.Left != nil {
			succ = succ.Left
		}
		root.Val = succ.Val
		root.Right = deleteNode(root.Right, succ.Val) // ...and delete it below
	}
	return root
}

为什么对

  1. 中序有序：对任意节点，中序先输出整棵左子树（都比它小），再输出它，再输出右子树（都比它大）；对每棵子树归纳，整个序列严格递增。
  2. 只和父节点比较不够：BST 要求整棵子树都落在祖先允许的范围内，所以要把 (lo, hi) 一路传下去。比如 [5, 1, 6, null, null, 3, 7]，3 比父节点 6 小，但它在 5 的右子树里，不合法。
  3. 查找每步只走一边，因为另一边整棵子树都不可能含目标，所以只走一条路径，O(h)。

30 秒口述稿

面试官让你讲思路时，按做法、为什么对、复杂度的顺序说。中英文各一版，可以对着读几遍。

中文
二叉搜索树最有用的性质是中序遍历有序，因为每个节点都是先输出更小的左子树、再输出自己、再输出更大的右子树。所以第 k 小、验证 BST、找前驱后继，我都转成中序遍历，用栈迭代可以在第 k 个时提前停下。验证时不能只和父节点比，要把上下界一路传下去。查找和插入只走一条路径，O(h)。
English
The most useful BST fact is that an inorder walk is sorted, since every node emits its smaller left subtree, then itself, then its larger right subtree. So I turn k-th smallest, validation and predecessor or successor into inorder walks, and an iterative walk with a stack can stop as soon as it reaches the k-th node. To validate, I pass lower and upper bounds down instead of comparing with the parent only. Search and insert follow a single path, which is O(h).

自评一下

对照上面的答案给自己打个分。没掌握的题会按 1、3、7、21 天的间隔回来，到期的题在「我的进度 · 到期复习」里。 只存在这台设备上；登录后会合并到你的账号。

对照要点（0/3）
这道题你会了吗？

小测

5 道概念题和复杂度题。答过的题会和 OA 选择题练习一起按间隔回来复习。 去 OA 选择题练习

5 道题
  1. 验证二叉搜索树时，只检查每个节点满足「左孩子 < 当前节点 < 右孩子」为什么不够？
  2. 把 1, 2, …, n 按顺序插入一棵不做平衡的普通二叉搜索树，树高（边数）是多少？
  3. 从 BST 中删除一个有两个孩子的节点，标准做法是？
  4. 这是一棵不做平衡的普通二叉搜索树。循环部分的总时间是？
    def insert(node, key):
    if not node:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)
    return node

root = None
for k in range(n):
    root = insert(root, k)
  5. 在 n 个节点、高度为 h 的 BST 上把 next() 调用 n 次走完整个中序。每次 next() 的代价是？
    class InorderIter:
    def __init__(self, root):
        self.stack = []
        self._push_left(root)

    def _push_left(self, node):
        while node:
            self.stack.append(node)
            node = node.left

    def next(self):
        node = self.stack.pop()
        self._push_left(node.right)
        return node.key

作答记录只保存在这台设备的浏览器里；登录后打开OA 选择题练习页，会存进账号。

模板练习

用上面的模板和变体出题：把打乱的行排回原序，把挖掉的边界条件填回去，或者在空白编辑器里整段默写，跑本站的测试并逐行对比。每次「换一题」都会重新出题。

下面几行被打乱了。点一行选中，再点另一行和它交换，排回模板原来的顺序；缩进是提示。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        node = node.right

分档练习

本站在 500 路里的 15 道题，按基础、核心、进阶分三档。每题附一句话思路，先自己想，想不出再看。

基础 4

#题目一句话思路难度分
700二叉搜索树中的搜索利用大小关系只搜索一个子树。
701二叉搜索树中的插入操作在保持BST有序性质的前提下插入新节点。
108将有序数组转换为二叉搜索树把有序数组按中点递归构造成高度平衡BST。
938二叉搜索树的范围和根据BST范围剪枝，避免遍历必然超出区间的子树。难度分 1335

核心 8

#题目一句话思路难度分
98验证二叉搜索树使用祖先上下界验证BST，避免只比较直接父子节点。
230二叉搜索树中第 K 小的元素利用中序有序性找到第k小元素并及时结束遍历。
530二叉搜索树的最小绝对差中序遍历比较相邻值，处理值为零、前驱初始化与最小差更新。
235二叉搜索树的最近公共祖先利用两个目标值与当前根的关系定位BST公共祖先。
285二叉搜索树中的中序后继 🔒查找中序后继，区分右子树存在与向祖先寻找更大值。
450删除二叉搜索树中的节点删除BST节点，分别处理零个、一个和两个孩子。
669修剪二叉搜索树根据值域裁剪BST，在删除根时保留仍有效的子树。
538把二叉搜索树转换为累加树逆中序累加更大值，理解遍历方向决定累加状态。

进阶 3

#题目一句话思路难度分
109有序链表转换二叉搜索树将有序链表转平衡BST，比较反复找中点与中序模拟的代价。
99恢复二叉搜索树通过中序逆序对定位两个被交换节点，覆盖相邻与非相邻交换。
426将二叉搜索树转化为排序的双向链表 🔒把BST原地转为有序循环双向链表，维护头尾及双向连接。