LeetCode 700. 二叉搜索树中的搜索

2021-11-21 HGNULB 约 9 分钟

文章信息 10 个分类 3 个标签

分类

LeetCode CodeTop 简单未解决 2-5 字节跳动微软阿里巴巴华为 LeetCode 75

题目描述

✅ 700. 二叉搜索树中的搜索

题意分析

给定一棵二叉搜索树的根节点 root 和一个整数 val，要求找到值等于 val 的那个节点，返回以它为根的子树；不存在时返回空。注意返回的是节点引用而不是布尔值，也不是新建的子树——直接把找到的节点原样交回去即可，它自带左右孩子，天然就是「以该节点为根的子树」。

题目最关键的信息藏在「二叉搜索树」这五个字里：对任意节点，左子树里所有值都严格小于它，右子树里所有值都严格大于它。这不是一句装饰性的背景说明，而是整道题的全部算法信号——它意味着每个节点的值都是一个分界点，拿目标值和它比一次，就能确定目标只可能在左边或只可能在右边，另一半可以整体丢弃。

题目还补充了节点值互不相同这一条。它保证了「找到就是唯一答案」，不必继续往下确认有没有第二个匹配，也保证了比较结果只有小于、等于、大于三种，不存在「相等但要往两边都找」的歧义。

数据规模上，节点数最多 5000，值域在 $[1, 10^7]$。这个规模其实随便什么做法都能过，所以考点显然不在效率极限，而在于你是否真的用上了 BST 的有序性：把整棵树遍历一遍找目标同样能 AC，却完全浪费了题目给的条件。

边界有三种：树本身为空、目标值不存在于树中、目标就在根节点上。前两种最终都表现为「走到空指针」，第三种则是第一次比较就命中。理想的实现应该让这三种情况全都由主循环自然处理掉，不需要任何额外的特判分支。

解法：迭代搜索

核心思路

先看不用 BST 性质的做法：把树当普通二叉树，做一次前序或层序遍历，逐个比较节点值。它一定正确，代价是访问全部 $n$ 个节点，时间 $O(n)$，还要额外的栈或队列空间。瓶颈在于每访问一个节点，只排除了这一个节点本身，信息利用率极低。

而 BST 的有序性给了强得多的信息。假设当前站在节点 cur 上，把 val 和 cur.val 比一次，三种结果各自能推出一个确定的结论：相等则 cur 就是答案，直接返回；val < cur.val 时，由「右子树所有值都大于 cur.val」可知右子树里每一个值都比 val 大，目标绝不可能在右边，于是整棵右子树连同 cur 一起被排除，搜索范围收缩到左子树；val > cur.val 对称，收缩到右子树。

关键在于「排除的是一整棵子树」而不是「一个节点」——每比较一次，候选集合就砍掉一大块，路径只会一直向下走，永不回头。既然不回头，就完全不需要栈来记录来路，一个游标指针足够，递归也就没有存在的必要。这是本题该写迭代而不是递归的根本原因。

循环不变量是：每次进入循环体时，若目标值存在于原树中，则它必定位于以 cur 为根的子树内。初始 cur = root，整棵树就是搜索范围，不变量成立；每一轮由上面的三段推理把范围换成左孩子或右孩子的子树，不变量得以保持。

有了这个不变量，两个出口的正确性就都清楚了：循环内命中相等时返回 cur 显然正确；循环因 cur == null 退出时，不变量说「若目标存在则它在空子树内」，而空子树里什么都没有，反推出目标根本不存在，返回空正确。

解题步骤

令游标 cur = root。用一个新变量而不是直接改 root，是为了不破坏入参、保留原始引用，在需要回头对照时更安全；语义上 cur 表示「当前搜索范围的根」。

循环条件写 cur != null，而不是 cur.left != null || cur.right != null 之类。用节点本身是否为空作条件，才能让「树为空」和「一路走到叶子外面」这两种情况共用同一个出口，也才不会在空树上直接空指针。

先判相等：cur.val == val 时立即返回 cur。相等分支必须排在前面单独处理，因为后面两个分支只区分大小，若把相等并进任意一边，命中的节点会被当成「不匹配」继续往下走，最终走到空返回 null。

val < cur.val 则 cur = cur.left。理由是右子树全体大于 cur.val，也就全体大于 val，不可能藏着目标。

否则 cur = cur.right。走到这个分支说明既不相等也不小于，即 val > cur.val，左子树全体小于 cur.val，同样被整体排除。

循环结束返回 null，表示遍历路径已走出树外，目标不存在。

以下面这棵树、val = 2 走一遍：根为 4，4 的左孩子是 2、右孩子是 7；2 的左孩子是 1、右孩子是 3。

初始 cur 指向 4。第一轮比较：4 != 2，且 2 < 4，于是排除 7 这整棵右子树，cur 移到 2。第二轮比较：2 == 2，命中，返回节点 2。返回的引用自带左孩子 1 和右孩子 3，也就是子树 [2, 1, 3]，正是题目要的答案。

再以同一棵树、val = 5 走一遍：cur = 4，5 > 4，移到 7；cur = 7，5 < 7，移到 7 的左孩子，而它为空；循环条件不满足，退出，返回 null。注意整个过程只碰了 2 个节点，1、2、3 这三个节点连看都没看——这就是有序性带来的收益。

最后以 root = null 走一遍：循环第一次判断就失败，直接返回 null。空树无需特判，主逻辑天然覆盖。

代码实现

class Solution {
    // 迭代向下查找直到找到目标或遇到空节点。
    public TreeNode searchBST(TreeNode root, int val) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val == val) {
                return cur;
            }
            if (val < cur.val) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        return null;
    }
}

func searchBST(root *TreeNode, val int) *TreeNode {
    // 迭代向下查找直到找到目标或遇到空节点。
    cur := root
    for cur != nil {
        if cur.Val == val {
            return cur
        }
        if val < cur.Val {
            cur = cur.Left
        } else {
            cur = cur.Right
        }
    }
    return nil
}

复杂度分析

时间复杂度：$O(h)$，$h$ 为树高。每轮循环只做一次比较和一次指针移动，全是常数操作，而 cur 每轮必定下降一层，所以循环次数不超过树高。树平衡时 $h = O(\log n)$；树退化成一条链时 $h = O(n)$，这是最坏情况——题目并不保证 BST 是平衡的。

空间复杂度：$O(1)$。全程只有 cur 一个指针变量，与节点数无关。这正是迭代写法相对递归写法的收益：递归虽然同样是 $O(h)$ 时间，却要付出 $O(h)$ 的调用栈，在退化成链的极端输入下有栈溢出风险。

关键点总结

BST 的核心价值在于「一次比较排除一整棵子树」，任何 BST 题的第一个自问都应该是「我用上有序性了吗」——如果解法换成普通二叉树也照样成立，那多半就没用上题目条件。

搜索路径单向下降、永不回溯，这个性质决定了不需要栈，因而可以写成 $O(1)$ 空间的迭代。凡是「只往一个方向走」的树上算法都适用这个转换。

相等判断必须独立成第一个分支，不能并入大于或小于任何一侧，否则命中的节点会被跳过。

循环条件用节点是否为空，能让空树、目标不存在这两种边界与主逻辑合流，无需特判——这是判断树上代码写得干不干净的一个通用标准。

面试视角：这道题本身几乎不构成考察，考官真正在等你补三句话——「时间是 $O(h)$ 不是 $O(\log n)$，因为树可能退化」「迭代版空间 $O(1)$，递归版 $O(h)$，所以我选迭代」「如果要保证 $O(\log n)$，需要 AVL 或红黑树这类自平衡结构」。答不出退化情形，是这题最常见的减分点。

易错点总结

循环条件写成 while (cur.left != null || cur.right != null)：输入 root = null 时第一次判断就空指针异常；即使树非空，目标恰在叶子上时也会因为叶子没有孩子而提前退出，返回 null 而不是该叶子。

相等分支并进小于分支：写成 if (val <= cur.val) cur = cur.left; else cur = cur.right;，对树 [4, 2, 7, 1, 3] 查 val = 4 会从 4 移到 2，再从 2 移到 1，再移到空，返回 null，而正确答案是根节点本身。

比较方向写反：写成 val < cur.val 时走右孩子，对树 [4, 2, 7] 查 val = 2 会从 4 移到 7，再移到空，返回 null；由于反向后仍然「有路可走」，代码不会崩，只会静默返回错误结果，最难排查。

返回新建节点而不是原节点：写成 return new TreeNode(cur.val)，对树 [4, 2, 7, 1, 3] 查 val = 2 会返回一个孤零零的 2，丢掉了孩子 1 和 3，与题目要求的「以该节点为根的子树」不符。

找到后没有立即返回而是继续下探：把 return cur 写成 ans = cur 却忘了 break，cur 会继续沿着大于分支走到空，若最后返回的是 cur 而非 ans，结果恒为 null。

递归版忘了把递归结果返回：写成 if (val < root.val) searchBST(root.left, val); 而不是 return searchBST(root.left, val);，对树 [4, 2, 7] 查 val = 2 会一路走到函数末尾返回 null，子调用的成功结果被整个丢弃。

递归版基线漏掉 root == null：只写 if (root.val == val) return root;，查一个不存在的值（如树 [4, 2, 7] 查 val = 5）会在走到空孩子时抛空指针异常。

Go 版返回 nil 时写成返回零值节点：写成 return &TreeNode{} 而非 return nil，调用方判空失败，会把一个值为 0 的假节点当成搜索结果。

忘记题目保证节点值唯一而写了「找到后还要看左子树有没有更早的」：对树 [4, 2, 7] 查 val = 2 会白白多走到 1 和空，虽然结果碰巧仍对，但把 $O(h)$ 退化成了一次多余下探，也说明没读懂约束。

相似题目

题目	难度	考察点
701. 二叉搜索树中的插入操作	中等	同样沿路径下降，但要在走到空位时挂上新节点并把父指针接好
450. 删除二叉搜索树中的节点	中等	找到之后还要按 0 / 1 / 2 个孩子分类，双孩子需用后继替换再递归删
98. 验证二叉搜索树	中等	反过来校验性质是否成立，需向下传递上下界而非只比父子两值
235. 二叉搜索树的最近公共祖先	中等	同样单向下降，分叉点（两值落在当前节点两侧）即答案
230. 二叉搜索树中第 K 小的元素	中等	用的是中序遍历的有序性而非单次大小比较，需要计数并提前终止
938. 二叉搜索树的范围和	简单	目标从单值变成区间，比较结果用于剪掉整边子树而不是选定唯一方向
108. 将有序数组转换为二叉搜索树	简单	逆向构造，取中点作根才能保证树高 $O(\log n)$，正好对应本题最坏情形的成因
704. 二分查找	简单	数组版的同一思想，BST 搜索就是把二分的中点固化成了树结构