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. 递归解法直觉IntuitionBST 的特殊性质决定了搜索策略对于当前节点如果目标值更小那么目标只可能出现在左子树如果更大只可能出现在右子树。因此每一步都可以丢弃一半的搜索空间。搜索过程要么在某层找到值相等的节点并返回它要么一路走到null指针——此时说明树中不存在该值返回null。算法步骤Algorithm若root为null或root.val等于目标值直接返回root。若目标值小于root.val递归搜索左子树。否则递归搜索右子树。返回递归调用的结果。多语言实现以下是原文档中给出的递归版本完整实现涵盖仓库支持的主流语言Python / Java / C / JavaScript / C# / Go / Kotlin / Swift / Rust# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # 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: OptionRcRefCellTreeNode, val: i32, ) - OptionRcRefCellTreeNode { 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使用OptionRcRefCellTreeNode包装需要通过borrow()读取节点值并在返回值前drop借用递归调用时克隆左右子树引用。这是 Rust 所有权模型下处理树的典型写法。仓库源码的另一种递归风格仓库中还收录了与上面略有差异的递归实现例如 java/0700-search-in-a-binary-search-tree.javapublic 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当root不为null且root.val不等于目标值时循环执行若目标值小于root.val将当前节点更新为root.left否则更新为root.right。循环结束后返回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 rootpublic 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: OptionRcRefCellTreeNode, val: i32, ) - OptionRcRefCellTreeNode { 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 迭代如何选择维度递归迭代时间复杂度O(H)O(H)空间复杂度O(H)调用栈O(1)代码风格简洁、与 BST 定义一一对应稍显过程化但更省内存适用场景思路讲解、树高可控平衡 BST树高较大、担心栈溢出时优先对于 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 有序性每次比较后只进入一个子树递归写法基线条件null 或命中 单向递归时间 O(H)、空间 O(H)迭代写法while 循环模拟下降时间 O(H)、空间 O(1)两个坑不要两边都搜访问val前必须判空仓库参考题解文档、Java 实现、Swift 实现本题虽然只有十几行代码却是理解 BST 全部后续算法插入、删除、验证、最近公共祖先等的基石。无论你用哪种语言、哪种写法只要牢牢抓住每次只走一条路这一条主线就不会出错。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考