二叉搜索树的搜索

力扣链接🔗

代码分析

递归法

1. 确定递归函数的参数和返回值

递归函数的参数传入的就是根节点和要搜索的数值，返回的就是以这个搜索数值所在的节点。

2. 确定终止条件

如果root为空，或者找到这个数值了，就返回root节点。

3. 确定单层递归的逻辑

如果root->val > val，搜索左子树，如果root->val < val，就搜索右子树，最后如果都没有搜索到，就返回NULL。

/**
 * 递归法
 *
 * @param root
 * @param val
 * @return
 */
public TreeNode searchBST(TreeNode root, int val) {
    // 找到值以后，停止递归
    if (root == null || root.val == val) {
        return root;
    }
    // 根据二叉搜索树的规律进行递归，注意使用了return，因为找到了就返回，不需要遍历整颗树
    if (root.val > val) return searchBST(root.left, val);
    if (root.val < val) return searchBST(root.right, val);
    // 没有找到
    return null;
}

迭代法

使用中序递归迭代即可。

/**
 * 递归法
 *
 * @param root
 * @param val
 * @return
 */
public TreeNode searchBST(TreeNode root, int val) {
    // 由于二叉搜索树已经确认了迭代的方向，所以不需要栈也不需要回溯
    while (root != null) {
        if (root.val > val) root = root.left;
        else if (root.val < val) root = root.right;
        else return root;
    }
    return null;
}