教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本文基于「宫水三叶的刷题日记」系列仓库 LogicStack-LeetCode 中的 LeetCode 700. 二叉搜索树中的搜索简单 题解展开。这是一道难度为「简单」、Tag 为「树的搜索 / 迭代 / 递归」的入门题给定一棵二叉搜索树BST的根节点和一个值在 BST 中查找节点值等于给定值的节点并返回以该节点为根的子树若节点不存在则返回NULL。读完本文你将掌握 BST 有序性在搜索场景下的核心运用以及递归与迭代两种写法的实现细节、复杂度差异与边界处理并能在本地基于该仓库的题解体系完成调试与提交。一、题目描述与核心语义给定二叉搜索树BST的根节点和一个值需要在 BST 中找到节点值等于给定值的节点返回以该节点为根的子树如果节点不存在则返回NULL。例如给定如下二叉搜索树4 / \ 2 7 / \ 1 3当给定值2时应返回如下子树2 / \ 1 3而当给定值为5时由于树中不存在值为5的节点应返回NULL。题目本身不复杂但它精准地考察了「二叉搜索树BST有序性」这一最本质的性质任意节点的左子树中所有节点值都小于该节点值任意节点的右子树中所有节点值都大于该节点值左、右子树本身也分别是二叉搜索树。正是这条性质使得我们可以在每一层比较当前节点值与目标值从而决定只向一侧子树继续搜索而不是像普通二叉树那样必须同时遍历左右两侧。这也是本题被归类为「树的搜索」系列的原因在 Index/树的搜索.md 的索引表中本题与 235. 二叉搜索树的最近公共祖先、938. 二叉搜索树的范围和 等题目共同构成了利用树结构与有序性进行定向搜索的题组。二、解法一递归搜索原题解给出的递归实现非常精简class Solution { public TreeNode searchBST(TreeNode root, int val) { if (root null || root.val val) return root; return root.val val ? searchBST(root.right, val) : searchBST(root.left, val); } }这段代码只有三行却完整覆盖了递归搜索的全部逻辑逐行拆解如下递归出口终止条件if (root null || root.val val) return root;root null表示已经越过叶子节点仍未找到目标值此时按题意返回NULLJava 中即nullroot.val val表示当前节点就是目标节点直接返回以它为根的整棵子树注意不是只返回该节点而是返回整棵子树这一点恰好呼应了题目「返回以该节点为根的子树」的要求。定向下降分治选择return root.val val ? searchBST(root.right, val) : searchBST(root.left, val);若当前节点值小于目标值根据 BST 有序性目标只可能出现在右子树于是递归右子树否则当前节点值大于目标值目标只可能出现在左子树于是递归左子树。这里利用原函数自身作为递归函数、复用root作为搜索过程中的当前节点是一种非常典型的 BST 问题写法。同样的「复用原函数 依据节点值大小定向下降」思路在仓库中 235. 二叉搜索树的最近公共祖先 的 DFS 解法中也有体现——不过那道题需要根据p、q两节点与当前根节点的值大小关系分三种情况讨论而本题只需与单一目标值比较逻辑更为直接。复杂度分析递归版时间复杂度$O(n)$其中 $n$ 为二叉树节点数。最坏情况下 BST 退化为单链例如仅含左子树或右子树的斜树需要沿链一路搜到底空间复杂度$O(n)$最坏情况下递归深度等于树高即退化链的长度忽略递归本身带来的额外空间开销后复杂度同样为 $O(n)$。需要说明的是上述 $O(n)$ 是最坏情况下的界。在 BST 保持平衡树高 $h O(\log n)$时实际搜索开销为 $O(h)$即 $O(\log n)$。三、解法二迭代搜索「迭代」是「递归」的等价改写。由于搜索方向在每一层都由「当前节点值与目标值的大小关系」唯一确定天然是一条从根向下的单一路径因此完全可以用while循环替代系统调用栈class Solution { public TreeNode searchBST(TreeNode root, int val) { while (root ! null root.val ! val) { root root.val val ? root.right : root.left; } return root; } }逐行拆解循环条件while (root ! null root.val ! val)等价于递归版的终止条件取反——只要当前节点非空且值不等于目标值就继续向下走单步下降root root.val val ? root.right : root.left;将指针移动到右子树或左子树其余节点包括兄弟子树、父节点路径上的其他节点全部不需要访问退出循环后return root;——退出可能有两种原因要么root恰好为目标节点root.val val要么已经走到底仍未见目标root null。两种情况下直接返回root都恰好满足题意返回子树或NULL因此无需额外判断分支。复杂度分析迭代版时间复杂度$O(n)$最坏情况同递归版需沿退化链遍历至底空间复杂度$O(1)$仅使用常数级别的指针变量不依赖递归调用栈这是迭代版相对递归版的核心优势。当树的规模很大、递归深度可能接近栈上限例如退化为单链且节点数达到数万级时迭代版是更稳妥的选择而递归版胜在代码与思维模型一一对应、可读性更强。四、两种解法的对比与边界情况梳理维度递归解法迭代解法实现方式复用原函数系统栈保存上下文while循环 指针移动时间最坏$O(n)$$O(n)$空间最坏$O(n)$递归栈深度$O(1)$代码可读性与递归语义直接对应逻辑直观需理解循环不变量适用场景树高可控、追求简洁树高可能很大、避免栈溢出边界情况自查清单root为空树null两种写法都会直接返回null符合「节点不存在返回 NULL」的题意目标值即根节点值递归版命中root.val val直接返回根迭代版因循环条件root.val ! val不成立同样直接返回根目标值位于叶子节点搜索会沿路径下降到叶子节点后命中目标值不存在递归版会在越过叶子后因root null返回null迭代版会在指针变为null时退出循环返回null目标值大于所有节点或小于所有节点搜索只会沿着最右或最左的单链一路下降最终返回null。五、仓库中的延伸与进阶路径本题位于「树的搜索」知识簇的入口位置围绕它可以在当前仓库中继续串联以下进阶题目形成完整的学习路径Index/树的搜索.md该索引表收录了 74、99、108、109、173、235、236、331、653、589、590、671、700、778、783、872、897、938、993 等树的搜索类题目按难度与推荐指数 数量排序是系统刷「树的搜索」专题的导航地图LeetCode/231-240/235. 二叉搜索树的最近公共祖先中等.md同样利用 BST 有序性定向搜索但目标从「单个值」升级为「两个节点的最近公共祖先」需要按当前根节点值与两节点值的关系分情况讨论可对比体会 BST 定向下降思想的推广LeetCode/691-700/700. 二叉搜索树中的搜索简单.md本题原题解可直接对照本文查看原始表述与系列文章说明仓库中 LeetCode/671-680 目录下的 671二叉树中第二小的节点、LeetCode/921-930 目录下的 938二叉搜索树的范围和等题目也都能复用「递归 依据有序性剪枝」的思维模式。六、本地调试与提交建议根据仓库 README.md 的介绍这是一个「日更」的算法仓库每篇题解对应一道 LeetCode 原题。在本地验证本文代码时可以按以下步骤操作在任意支持 Java 的 IDE或 LeetCode 在线编辑器中将Solution类连同TreeNode定义一起粘贴按题目给定的root数组如[4,2,7,1,3]构造二叉搜索树注意数组中的null表示空位需要按层序建树分别调用递归版与迭代版searchBST用示例val 2验证返回子树为2 → 1, 3用val 5验证返回null补充自测用例空树root []、单节点树、退化为单链的 BST如[1,null,2,null,3]确认两种写法均不越界、不抛异常。总结LeetCode 700 虽然难度为简单却是理解「BST 有序性驱动定向搜索」这一核心思想的经典入口递归版以三行代码展示分治语义迭代版以 $O(1)$ 空间展示栈的等价消除。结合 LogicStack-LeetCode 仓库的 树的搜索索引 与 235 题解 等延伸内容读者可以以此为起点逐步掌握整棵二叉搜索树家族题目的统一思维框架。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐LogicStack-LeetCode 刷穿 LeetCode938. 二叉搜索树的范围和简单——BST 中序遍历的递归与迭代双解法LogicStack LeetCode 刷穿 LeetCode938. 二叉搜索树的范围和简单——BST 中序遍历的递归与迭代双解法 本文是「宫水三叶的刷教程文档Docker 引擎插件全生命周期管理docker-py 的 client.plugins 实战指南Docker 引擎插件全生命周期管理docker py 的 client.plugins 实战指南 导读 Docker Engine 插件Plugin是扩教程文档LeetCode 235 二叉搜索树最近公共祖先LCA基于 BST 有序性的递归与迭代双解法详解LeetCode 235 二叉搜索树最近公共祖先LCA基于 BST 有序性的递归与迭代双解法详解 本篇文章聚焦 LeetCode 235「二叉搜索树的最近示例工程教程上一篇G-Helper终极指南华硕笔记本轻量级控制工具完全解析下一篇Scarab终极指南空洞骑士模组管理的完整教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考