700. 二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

示例 1:

输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]
示例 2:

输入：root = [4,2,7,1,3], val = 5
输出：[]

提示：

树中节点数在 [1, 5000] 范围内
1 <= Node.val <= 107
root 是二叉搜索树
1 <= val <= 107

解题思路

这题是简单题， 不用很多技巧。

从“盲目翻找”到“精准导航”：小白也能看懂的二叉搜索树（BST）搜索推导

在刚开始刷树相关的算法题时，很多人一看到“查找节点”，第一反应往往是：直接遍历整棵树呗！递归前序遍历、中序遍历，或者用队列做层序遍历，搜一遍不就找到了吗？

然而，当刷到 700. 二叉搜索树中的搜索 这道题时，你会发现题目里多了一个关键的前缀词——二叉搜索树（Binary Search Tree, 简称 BST）。

这个前缀并不是摆设，它实际上赋予了这棵树一种“自动导航”的能力。本文将站在初学者的视角，一步步推导如何利用这个特性，把原本需要盲目翻找的过程，变成优雅且高效的精准定位。

---

一、 拆解题目：为什么不能“暴力搜”？

假设我们要在树中寻找目标值 val：

• 普通二叉树：就像在一个乱七八糟的房间里找钥匙，由于节点值没有任何规律，我们只能无脑遍历左子树和右子树，最坏情况下要把所有节点都访问一遍，时间复杂度是 $O(N)$。
• 二叉搜索树（BST）：如同排好序的书架。它有一条至关重要的核心性质：
  1. 若左子树不为空，则左子树上所有节点的值均小于根节点的值。
  2. 若右子树不为空，则右子树上所有节点的值均大于根节点的值。
  3. 它的左右子树也分别是一棵二叉搜索树。

这意味什么？
只要我们站在某个节点上，拿着目标值 val 和当前节点值 root.val 做个对比，就能立刻知道下一步该往哪走：

• 如果 val < root.val：目标只可能藏在左子树，右子树可以直接全盘放弃！
• 如果 val > root.val：目标只可能藏在右子树，左子树可以直接扔掉！
• 如果 val == root.val：运气真好，直接命中，返回当前节点。

这不就是数组里的二分查找（Binary Search）在树形结构上的应用吗？每一次比较，都能斩断一半的搜索路径。

---

二、 逻辑推导：从直觉到递归实现

明白了导航规则后，我们尝试用最符合人类思维习惯的递归来表达这个过程。

写递归代码时，新手容易陷进递归细节里“人肉递归”。其实只要明确两点：出口条件和单层逻辑。

1. 递归出口（终点）

在什么情况下查找会停止？

• 找不到：一路往下走，走到了空节点（root == null），说明树里根本没有这个值，返回 null。
• 找到了：当前节点的值刚好等于目标值（root.val == val），找到了要找的节点，直接返回 root。

2. 单层分支逻辑（方向选择）

• 如果 val < root.val：向左走，递归搜索左子树 searchBST(root.left, val)。
• 如果 val > root.val：向右走，递归搜索右子树 searchBST(root.right, val)。

Java 递归代码实现

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        // 1. 终止条件：节点为空 或 找到目标节点
        if (root == null || root.val == val) {
            return root;
        }
        // 2. 根据 BST 特性选择导航方向
        if (val < root.val) {
            return searchBST(root.left, val);
        } else {
            return searchBST(root.right, val);
        }
    }
}

时间复杂度：平均 O(log N)（跟树的高度相关）；最坏情况（树退化成单链表）为 O(N)。

三、 进阶思考：能不能不用递归？（迭代法）

写完递归代码后，不少新手会疑惑：“普通二叉树的遍历如果要改成迭代（循环），通常需要自己维护一个显式 Stack 或 Queue，这道题也需要吗？”

答案是：完全不需要！

为什么？因为普通二叉树在遍历时需要“回溯”（访问完左子树还要折返回来找右子树），所以必须用栈记录来时路。而 BST 的搜索方向是单一且明确的——我们要么往左，要么往右，绝不回头。

这就意味着，我们只需要用一个 while 循环，让 root 指针顺着方向一直向下移动即可，连额外的栈空间都不用开辟！

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        // 当 root 不为空，且还没找到目标值时，持续向下探索
        while (root != null && root.val != val) {
            if (val < root.val) {
                root = root.left;   // 目标值较小，往左走
            } else {
                root = root.right;  // 目标值较大，往右走
            }
        }
        // 循环结束时，root 要么是找到的节点，要么是 null（未找到）
        return root;
    }
}

空间复杂度：降到了真正的 O(1)，没有额外的栈开销，性能和可读性兼备。

欢迎关注个人公众号