LeetCode 700. 二叉搜索树中的搜索

Categories:

题目描述
思路分析
1. 解法一：迭代搜索（推荐）
相似题目

题目描述

✅ 700. 二叉搜索树中的搜索

思路分析

解法一：迭代搜索（推荐）

核心思路：

利用二叉搜索树性质：目标值小则往左，大则往右。

迭代向下查找直到找到目标或遇到空节点。

复杂度分析：

时间复杂度：O(h)，其中 h 表示树的高度。

空间复杂度：O(1)，仅使用常数额外空间。

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
}

相似题目

题目	难度	考察点
701. 二叉搜索树中的插入操作	中等	二叉搜索树
98. 验证二叉搜索树	中等	二叉搜索树
230. 二叉搜索树中第 K 小的元素	中等	二叉搜索树
450. 删除二叉搜索树中的节点	中等	二叉搜索树
235. 二叉搜索树的最近公共祖先	简单	二叉搜索树

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/75827122