LeetCode 700. 二叉搜索树中的搜索
题目描述
题意分析
在给定二叉搜索树中查找值为
val的节点。找到时返回这个节点本身，也就同时返回了以它为根的原有整棵子树；不存在时返回空节点。题目已经保证输入是二叉搜索树：任意节点左子树中的所有值都小于它，右子树中的所有值都大于它。任务只做查找，不需要重新验证树、复制节点或改变任何连接。
解法：迭代搜索
核心思路
[!blue]
用一个游标
cur指向当前仍可能包含目标的子树根。若当前值等于目标，直接返回当前节点；若目标更小，当前节点及整个右子树都不可能命中，只需进入左子树；若目标更大，同理只进入右子树。排除依据来自整棵子树的大小约束，而不只是当前节点与两个孩子的比较。因此每次只选择一个方向，就已经覆盖了所有剩余可能性，无需同时搜索两边或事后回到另一边。
游标每轮向下一层移动，最终要么命中，要么走到空节点。到达空节点意味着唯一可能的搜索分支也已经耗尽，可以返回空。过程中没有回溯需求，迭代只用一个节点引用；返回原引用会保留目标节点已有的全部后代。
解题步骤
- 令
cur = root。- 当前节点非空时，先比较节点值与目标，相等就直接返回
cur。- 目标较小时令
cur = cur.left，较大时令cur = cur.right。- 游标变为空后返回空节点，表示目标不存在。
代码实现
class Solution {
// 迭代向下查找直到找到目标或遇到空节点。
public TreeNode searchBST(TreeNode root, int val) {
TreeNode cur = root;
while (cur != null) {
// 返回原节点，连同它已有的左右子树一起交回
if (cur.val == val) {
return cur;
}
if (val < cur.val) {
cur = cur.left;
} else {
cur = cur.right;
}
}
return null;
}
}
func searchBST(root *TreeNode, val int) *TreeNode {
// 迭代向下查找直到找到目标或遇到空节点。
cur := root
for cur != nil {
// 返回原节点，连同它已有的左右子树一起交回
if cur.Val == val {
return cur
}
if val < cur.Val {
cur = cur.Left
} else {
cur = cur.Right
}
}
return nil
}
复杂度分析
- 时间复杂度：$O(h)$，
h为树高，只沿一条根到叶路径下降。平衡树为 $O(\log n)$，退化为链时为 $O(n)$。- 空间复杂度：$O(1)$，只使用一个移动游标，没有递归栈。
关键点总结
[!green]
- BST 的整棵子树有序性，使一次比较能够安全排除另一侧。
- 返回目标的原节点，才能把以它为根的完整子树一起返回。
- 向下一层不代表候选节点数量减半，时间由实际树高决定。
易错点总结
[!yellow]
- 把比较方向写反，会进入已经被大小关系排除的子树。
- 只在当前节点有孩子时循环，会遗漏自身就是目标的叶子节点。
- 创建一个值相同的新节点返回，会丢掉原目标节点下面应保留的子树。
- 无条件遍历两棵子树，放弃了输入已提供的有序性，增加不必要的搜索。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 98. 验证二叉搜索树 | 中等 | 搜索依赖BST的全局有序性质，原题验证这一性质而非定位单个值。 |
| 701. 二叉搜索树中的插入操作 | 中等 | 搜索到空位置后即可完成插入，沿左右分支下降的规则相同。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！