700. 二叉搜索树中的搜索

àì夳堔傛蜴生んèń 2023-02-18 03:09 82阅读 0赞

# 题目来源 #

[700. 二叉搜索树中的搜索][700.]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

# 题目解析 #

## 递归 ##

首先判空，如果当前结点不存在，直接返回空。如果当前结点值等于目标值，返回当前结点。接下来就看如果当前结点值大于目标值，则对左子结点调用递归函数，否则就对右子结点调用递归函数

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

![在这里插入图片描述][20200615170052529.png]

## 迭代 ##

不需要已经判断过的节点，因为使用while就可以将递归改成迭代了；  
如果需要回到已经遍历过的节点，对于相关递归，就需要一个栈来存储之前的节点

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

![在这里插入图片描述][20200615170542157.png]

[700.]: https://leetcode-cn.com/problems/search-in-a-binary-search-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200615170614846.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200615170052529.png]: https://img-blog.csdnimg.cn/20200615170052529.png
[20200615170542157.png]: https://img-blog.csdnimg.cn/20200615170542157.png