LeetCode 700简单二叉树 · BST
二叉搜索树中的搜索 图解题解
这道题到底在问什么
给一棵二叉搜索树的根 root 和一个目标值 val,找到值等于 val 的那个节点,返回以它为根的子树;找不到就返回空。
- 树
- [8,3,10,1,6,null,14]
- val
- 6
- 输出
- 节点 6(及其子树)
先想最直接的笨办法
如果当成普通二叉树,你得挨个节点比对,最坏要看完全部 n 个节点。但这是搜索树,有序,完全用不着这么笨。（动画第 3 步）
最优解：一步一步想明白
- 3如果当成普通二叉树,你得挨个节点比对,最坏要看完全部 n 个节点。但这是搜索树,有序,完全用不着这么笨。
- 4就像查字典:你不会从第一页翻到最后一页,而是看一眼当前页比目标大还是小,直接决定往前还是往后翻。BST 查找就是这个直觉。
- 5盯住当前节点(橙色高亮的那个)和它跟 6 的大小关系:小了往右下、大了往左下,走过的路径会被点亮。
- 6左小右大,处处成立先认清结构:根 8 的左子树(蓝)1、3、6 全比 8 小,右子树(绿)10、14 全比 8 大。这条「左小右大」在每个节点都成立,正是查找能排除一整侧不可能子树的依据。
- 7cur = 8,目标 val = 6查找永远从根开始。当前节点是 8,把目标 6 和它比。
- 8右子树 10、14 整块排除6 比 8 小。按「左小右大」,6 绝不可能在右边——右子树 10、14 整块作废(紫色标记),一次比较排除一整侧。
- 96 比 8 小,去左子树当前节点下移到 8 的左孩子 3。8 已访问(蓝),被排除的 10、14 保持作废标记。再拿 6 和 3 比。
- 103 的左孩子 1 排除6 比 3 大,该往右。3 的左孩子 1 也被排除,又砍掉一块。
- 11当前来到 6当前节点来到 3 的右孩子 6。已经把整棵树砍得只剩这一条路了。
- 12找到了:返回节点 6当前节点的值正好等于 6,命中(绿色)!整棵 7 个节点的树,我们只比较了 3 次(8 → 3 → 6),其余节点看都没看。返回这个节点连同它的子树。
- 13命中很爽,但找不到的情况也要会处理。同一套规则,找一个树里没有的 5。
- 14cur = 8,目标 val = 5重新从根 8 开始查找,这次目标换成 5,看它最后怎么走到空。
- 155 比 8 小,去左子树5 比 8 小,和找 6 那次一样往左走,右子树作废,当前节点下移到 3。
- 16节点 1 排除5 比 3 大,和找 6 时一样该往右走,3 的左孩子节点 1 被排除作废。
- 17当前到 6当前节点移动到 3 的右孩子 6,继续拿它和目标 5 比。
- 18当前 6,5 比它小当前到了 6,但 6 ≠ 5,还没结束。5 比 6 小,按规则该往 6 的左孩子走。
- 196 没有左孩子 → 走到空可 6 根本没有左孩子,下一步是空节点。走到空就说明:这棵树里没有 5,返回空。这正是查找的终止条件。
- 20若不利用有序 → 全看一遍如果无视「左小右大」、把它当普通二叉树遍历,你得把所有节点都比一遍(O(n))。BST 查找之所以快,全靠每一步用大小关系扔掉一整侧不可能的子树。下面用一行数组把两者的差距摆出来。
- 21把节点摊平,逐个比把 6 个节点摊成一排,线性查找就是指针从左到右一个个比。最坏(目标在末尾或不存在)要比完全部 6 个。
- 22指针挪到 3第 1 个 1 不对,指针前移到 3。线性查找老老实实一个个挪,不会跳。
- 23线性扫描进行中指针挪到第 4 个 8,前面 1、3、6 都白比了。线性查找不会「跳过」任何元素。
- 24最坏比完 6 个最坏情况指针一路扫到最后的 14,前面全比过——这就是 O(n)。元素越多越慢。
- 25对比:走树只比 3 次而走 BST 找 6,只碰了 8、3、6 三个(高亮),其余灰格连看都没看。树越大,这个差距越夸张——这就是「有序 + 每步排除一整侧」的威力。
- 268 → 3 → 6,三步到位回看命中那条路径:8 → 3 → 6,从根到目标一条线。比较次数 = 走过的层数 = 树高。树越平衡,树高越低(O(log n))。
- 27它和有序数组上的二分查找思路相通:二分每次稳稳砍掉一半,BST 砍掉的是一整侧子树——只有树平衡时才接近一半。想通这点,「二叉搜索树为什么快、又为什么会变慢」就再不神秘。
- 316 < 8 却往右 → 跑错方向若把方向写反:6 比 8 小本该往左,却跑到右边的 10。这条路上全是比 8 大的数,永远碰不到 6。记牢:小往左、大往右。
⚠️ 容易写错的地方
✗ 错：while root.val != val
✓ 对：while root && root.val != val
没找到会走到空节点,先判 root 非空再读 .val,否则空指针崩溃
✗ 错：比较方向写反:小往右、大往左
✓ 对：val < root.val 往左,否则往右
BST 左小右大,方向反了直接查不到
完整代码（Python / C++ / Java）
Python
class Solution:
def searchBST(self, root, val):
while root and root.val != val: # 没到空、也没命中
if val < root.val: # 目标更小 → 往左
root = root.left
else: # 目标更大 → 往右
root = root.right
return root # 命中返回该节点, 否则 NoneC++
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
while (root && root->val != val) { // 没到空也没命中
if (val < root->val) root = root->left; // 更小往左
else root = root->right; // 更大往右
}
return root; // 命中或 nullptr
}
};Java
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
while (root != null && root.val != val) { // 没到空也没命中
if (val < root.val) root = root.left; // 更小往左
else root = root.right; // 更大往右
}
return root; // 命中或 null
}
}复杂度
时间复杂度
O(h) = O(log n) 均衡 / O(n) 退化
每步下降一层,比较次数 = 走过的树高 h。均衡树 h≈log n;退化成链则 h=n
空间复杂度
O(1)
迭代写法只用一个指针 root,不开递归栈、不开额外结构
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 二叉搜索树中的搜索 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
迭代和递归两种写法哪个好?+
逻辑一样;迭代空间 O(1),递归会有 O(h) 栈开销,面试常被要求写迭代版。
查找复杂度为什么是 O(h) 不是 O(log n)?+
O(log n) 只在树平衡时成立;不平衡时 h 可能到 n,所以严谨说法是 O(h)。
怎么保证 BST 一直平衡?+
用自平衡结构,如 AVL 树、红黑树,插入删除时旋转维持高度 O(log n)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 二叉搜索树中的搜索 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。