700.二叉搜索树中的搜索

谁借莪１个温暖的怀抱￠ 2023-10-16 10:40 36阅读 0赞

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

*  题干描述
 *  解题思路
 *   *  二叉搜索树的特点
     *  递归法
     *   *  1. 确定递归函数的参数和返回值
         *  2. 确定终止条件
         *  3. 确定单层递归的逻辑
     *  迭代法
 *  代码实现
 *   *  递归法
     *  利用二叉搜索树特点的递归法
     *  基于普通二叉树特点的迭代法
     *  利用二叉搜索树特点的迭代法

## 题干描述 ##

[700.二叉搜索树中的搜索-力扣入口][700._-]

给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。

例如，  
![在这里插入图片描述][25b8bf4205a04156954443fbe7f659d0.png]  
在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。

## 解题思路 ##

之前我们讲的都是普通二叉树，那么接下来看看二叉搜索树。

### 二叉搜索树的特点 ###

*  若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
 *  若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
 *  它的左、右子树也分别为二叉搜索树

### 递归法 ###

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

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

#### 2. 确定终止条件 ####

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

#### 3. 确定单层递归的逻辑 ####

二叉搜索树中的节点是有序的，所以可以有方向地去搜索。

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

很多同学习惯直接写`searchBST(root->left, val)`，却忘了递归函数还有返回值。如果不用一个变量将其接住，那么搜索到的val就没有存储。

### 迭代法 ###

一提到二叉树遍历的迭代法，可能立刻想起使用栈来模拟深度遍历，使用队列来模拟广度遍历。

对于二叉搜索树可就不一样了，因为二叉搜索树的特殊性，也就是节点的有序性，可以不使用辅助栈或者队列就可以写出迭代法。

对于一般二叉树，递归过程中还有回溯的过程，例如走一个左方向的分支走到头了，那么要调头，在走右分支。

而**对于二叉搜索树，不需要回溯的过程，因为节点的有序性就帮我们确定了搜索的方向。**

## 代码实现 ##

### 递归法 ###

public TreeNode searchBST(TreeNode root, int val){
        
        if(root == null || root.val == val){
        
            return root;
        }
        TreeNode left = searchBST(root.left, val);
        if(left != null){
        
            return left;
        }
        return searchBST(root.right, val);
    }

### 利用二叉搜索树特点的递归法 ###

public TreeNode searchBST(TreeNode root, int val){
        
        if(root == null || root.val == val){
        
            return root;
        }
        if(val < root.val){
        
            return searchBST(root.left, val);
        } else{
        
            return searchBST(root.right, val);
        }
    }

### 基于普通二叉树特点的迭代法 ###

// 700.二叉搜索树中的搜索 - 迭代，普通二叉树
    public TreeNode searchBST(TreeNode root, int val){
        
        if(root == null || root.val == val){
        
            return root;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
        
            TreeNode pop = stack.pop();
            if(pop.val == val){
        
                return pop;
            }
            if(pop.right != null){
        
                stack.push(pop.right);
            }
            if(pop.left != null){
        
                stack.push(pop.left);
            }
        }
        return null;
    }

### 利用二叉搜索树特点的迭代法 ###

public TreeNode searchBST(TreeNode root, int val){
        
        while(root != null)
            if(val < root.val) root = root.left;
            else if(val > root.val) root = root.right;
            else return root;
            return null;
    }

**参考资料**：[代码随想录-700.二叉搜索树中的搜索][-700.]

[700._-]: https://leetcode.cn/problems/search-in-a-binary-search-tree/
[25b8bf4205a04156954443fbe7f659d0.png]: https://img-blog.csdnimg.cn/25b8bf4205a04156954443fbe7f659d0.png
[-700.]: https://programmercarl.com/0700.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%90%9C%E7%B4%A2.html