LeetCode 0700 二叉搜索树搜索（Search in a Binary Search Tree）多语言题解：递归与迭代两种实现

LeetCode 0700 二叉搜索树搜索（Search in a Binary Search Tree）多语言题解：递归与迭代两种实现

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本文围绕 LeetCode 0700「Search in a Binary Search Tree」展开，基于当前仓库的 题解文档 与其配套源码，系统讲解在二叉搜索树（BST）中查找目标节点的两种标准写法——递归与迭代。读完本文，你将掌握利用 BST 有序性将查找复杂度收敛到 O(H)（H 为树高）的核心思路，理解两种写法的复杂度差异与适用场景，并能直接套用仓库中 Python、Java、C++、JavaScript、C#、Go、Kotlin、Swift、Rust 九种语言的现成实现。

前置知识：解题前需要掌握的概念

原文档要求读者在动手之前先熟悉以下三个基础，这也是几乎所有 BST 类问题（如 插入节点、验证二叉搜索树）的公共前提：

• 二叉搜索树（BST）性质：对于任意节点，其左子树的所有值都小于该节点值，右子树的所有值都大于该节点值。这是整个搜索过程能够"每次排除一半子树"的理论根基。
• 树遍历：能够通过 left/right 孩子指针在节点间移动，理解沿路径下降的过程。
• 递归：能够用递归函数处理树结构，并正确设置基线条件（base case）来终止递归。

这三个概念分别对应了本问题的三个关键词：凭什么能二分（BST 性质）、怎么走（指针/遍历）、怎么写（递归或循环）。

1. 递归解法

直觉（Intuition）

BST 的特殊性质决定了搜索策略：对于当前节点，如果目标值更小，那么目标只可能出现在左子树；如果更大，只可能出现在右子树。因此每一步都可以丢弃一半的搜索空间。搜索过程要么在某层找到值相等的节点并返回它，要么一路走到null指针——此时说明树中不存在该值，返回null。

算法步骤（Algorithm）

1. 若root为null，或root.val等于目标值，直接返回root。
2. 若目标值小于root.val，递归搜索左子树。
3. 否则，递归搜索右子树。
4. 返回递归调用的结果。

多语言实现

以下是原文档中给出的递归版本完整实现，涵盖仓库支持的主流语言（Python / Java / C++ / JavaScript / C# / Go / Kotlin / Swift / Rust）：

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]: if not root or root.val == val: return root return self.searchBST(root.left, val) if val < root.val else self.searchBST(root.right, val)

public class Solution { public TreeNode searchBST(TreeNode root, int val) { if (root == null || root.val == val) { return root; } return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val); } }

class Solution { public: TreeNode* searchBST(TreeNode* root, int val) { if (!root || root->val == val) { return root; } return val < root->val ? searchBST(root->left, val) : searchBST(root->right, val); } };

class Solution { /** * @param {TreeNode} root * @param {number} val * @return {TreeNode} */ searchBST(root, val) { if (!root || root.val === val) { return root; } return val < root.val ? this.searchBST(root.left, val) : this.searchBST(root.right, val); } }

public class Solution { public TreeNode SearchBST(TreeNode root, int val) { if (root == null || root.val == val) { return root; } return val < root.val ? SearchBST(root.left, val) : SearchBST(root.right, val); } }

func searchBST(root *TreeNode, val int) *TreeNode { if root == nil || root.Val == val { return root } if val < root.Val { return searchBST(root.Left, val) } return searchBST(root.Right, val) }

class Solution { fun searchBST(root: TreeNode?, `val`: Int): TreeNode? { if (root == null || root.`val` == `val`) { return root } return if (`val` < root.`val`) searchBST(root.left, `val`) else searchBST(root.right, `val`) } }

class Solution { func searchBST(_ root: TreeNode?, _ val: Int) -> TreeNode? { guard let root = root else { return nil } if root.val == val { return root } return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val) } }

impl Solution { pub fn search_bst( root: Option<Rc<RefCell<TreeNode>>>, val: i32, ) -> Option<Rc<RefCell<TreeNode>>> { match root { None => None, Some(node) => { let n = node.borrow(); if n.val == val { drop(n); Some(node) } else if val < n.val { Self::search_bst(n.left.clone(), val) } else { Self::search_bst(n.right.clone(), val) } } } } }

说明：Rust 由于TreeNode使用Option<Rc<RefCell<TreeNode>>>包装，需要通过borrow()读取节点值，并在返回值前drop借用；递归调用时克隆左右子树引用。这是 Rust 所有权模型下处理树的典型写法。

仓库源码的另一种递归风格

仓库中还收录了与上面略有差异的递归实现，例如 java/0700-search-in-a-binary-search-tree.java：

public TreeNode searchBST(TreeNode root, int val) { if (root == null) { return root; } else if (root.val < val) { return searchBST(root.right, val); } else if (root.val > val) { return searchBST(root.left, val); } return root; }

这种写法把三种情况显式拆开：先判空、再判断"目标更大→向右""目标更小→向左"，最后剩下的情况即root.val == val，返回root。swift/0700-search-in-a-binary-search-tree.swift 也采用了同样的先判空、再比较大小的结构：

class Solution { func searchBST(_ root: TreeNode?, _ val: Int) -> TreeNode? { if root == nil { return nil } if val > root!.val { return searchBST(root?.right, val) } else if val < root!.val { return searchBST(root?.left, val) } else { return root } } }

两种递归风格逻辑完全等价，区别仅在于比较顺序与返回写法：合并式把"为空或命中"合并为一个基线条件，拆分式则显式枚举三种分支。面试中两种都可接受，建议按自己最不易出错的习惯选择。

复杂度分析

• 时间复杂度：O(H)，其中 H 为给定树的高度。每一步只沿一条路径下降，不会回溯。
• 空间复杂度：O(H)，来自递归调用栈的深度。

注意这里的 H 是树高。在平衡 BST 中 H ≈ log₂N，此时时间复杂度近似 O(log N)；但在退化成链的树中 H = N，最坏为 O(N)。原文档统一用 O(H) 表述，是最严谨的写法。

2. 迭代解法

直觉（Intuition）

递归的本质是借助调用栈保存"剩余工作"。本问题的搜索路径是单条的——每一步只有唯一的去向（左或右），因此完全可以用一个while循环模拟递归过程：用局部变量代替调用栈。这样既避免了递归调用本身的函数栈开销，也把额外空间降到常数级。

算法步骤（Algorithm）

1. 当root不为null且root.val不等于目标值时，循环执行：
   • 若目标值小于root.val，将当前节点更新为root.left；
   • 否则更新为root.right。
2. 循环结束后返回root——它要么是找到的目标节点，要么是null（表示未找到）。

多语言实现

以下是原文档给出的迭代版本完整实现：

class Solution: def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]: while root and root.val != val: root = root.left if val < root.val else root.right return root

public class Solution { public TreeNode searchBST(TreeNode root, int val) { while (root != null && root.val != val) { root = val < root.val ? root.left : root.right; } return root; } }

class Solution { public: TreeNode* searchBST(TreeNode* root, int val) { while (root && root->val != val) { root = val < root->val ? root->left : root->right; } return root; } };

class Solution { /** * @param {TreeNode} root * @param {number} val * @return {TreeNode} */ searchBST(root, val) { while (root != null && root.val != val) { root = val < root.val ? root.left : root.right; } return root; } }

public class Solution { public TreeNode SearchBST(TreeNode root, int val) { while (root != null && root.val != val) { root = val < root.val ? root.left : root.right; } return root; } }

func searchBST(root *TreeNode, val int) *TreeNode { for root != nil && root.Val != val { if val < root.Val { root = root.Left } else { root = root.Right } } return root }

class Solution { fun searchBST(root: TreeNode?, `val`: Int): TreeNode? { var node = root while (node != null && node.`val` != `val`) { node = if (`val` < node.`val`) node.left else node.right } return node } }

class Solution { func searchBST(_ root: TreeNode?, _ val: Int) -> TreeNode? { var node = root while node != nil && node!.val != val { node = val < node!.val ? node!.left : node!.right } return node } }

impl Solution { pub fn search_bst( root: Option<Rc<RefCell<TreeNode>>>, val: i32, ) -> Option<Rc<RefCell<TreeNode>>> { let mut cur = root; while let Some(node) = cur { let n = node.borrow(); if n.val == val { drop(n); return Some(node); } else if val < n.val { cur = n.left.clone(); } else { cur = n.right.clone(); } } None } }

迭代版本各语言要点：

• Kotlin / Swift 需要引入一个var可变变量（如node/cur）来在循环中不断移动"当前指针"，因为原入参在 Kotlin 中为只读引用。
• Swift 在循环体内使用node!强制解包是安全的，因为循环条件已保证node != nil。
• Rust 版本在命中时先drop(n)释放借用再返回Some(node)，避免借用冲突；未命中则沿left/right继续，循环结束后返回None。

复杂度分析

• 时间复杂度：O(H)，与递归版本相同，H 为树高。
• 空间复杂度：O(1)额外空间，因为没有使用调用栈，只占用常量级的指针变量。

递归 vs 迭代如何选择

对于 0700 这道题，两种写法都很短；工程上如果树可能退化为长链（H 接近 N），迭代的 O(1) 空间优势会体现为不会触发递归栈溢出。

常见陷阱（Common Pitfalls）

陷阱一：忽略 BST 性质，当成普通二叉树搜索

如果把这道题当成普通二叉树搜索——在每个节点同时探查左右两个孩子——就完全失去了 BST 结构的意义。BST 性质保证目标值只可能出现在其中一个子树：值小于当前节点就去左边，大于就去右边。任何"两边都查"的写法都会把复杂度从 O(H) 恶化到 O(N)，并且没有利用题目给出的有序结构。判断方向永远只需要一次val与root.val的比较。

陷阱二：忘记处理 null 情况

在访问root.val之前不检查root是否为null，会导致空指针异常（null pointer exception）。这个检查有两重身份：

• 在递归写法中，它是基线条件：树中找不到目标值、一路走到叶子之下时，null就是递归的终止点；
• 在迭代写法中，它是循环终止条件：while (root != null && root.val != val)中的root != null保证循环安全退出。

原文档中的两份参考实现（Java 版、Swift 版）也都把判空放在第一行，可见这是所有正确实现共有的前提。

延伸：本题在 BST 系列中的位置

0700 是 BST 系列里最基础的一道"读操作"，与仓库中的其他 BST 文章形成完整的知识闭环：

• 学会搜索（本题）之后，可继续学习 向 BST 插入节点：插入算法复用了完全相同的"比较大小→决定方向→走到 null 为止"的框架，区别仅在于到达空位时是"返回 null"还是"新建节点"；
• 反过来，验证二叉搜索树 则考察你是否真正理解 BST 性质：它要求用区间约束（最小值/最大值）递归校验整棵树，是 0700 反向思维的高级形态。

建议按「搜索 → 插入 → 验证」的顺序刷题，三题合起来能让你把 BST 的"读、写、校验"三种基本操作一次性打通。

小结

本题虽然只有十几行代码，却是理解 BST 全部后续算法（插入、删除、验证、最近公共祖先等）的基石。无论你用哪种语言、哪种写法，只要牢牢抓住"每次只走一条路"这一条主线，就不会出错。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode