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

墨蓝 2023-10-08 16:13 5阅读 0赞

## 1 题目描述 ##

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/search-in-a-binary-search-tree

## 2 题目示例 ##

![在这里插入图片描述][53537f18afbd4933a098fac6e4df578f.png]  
![在这里插入图片描述][199e3fa3a5b0418697bf67744cf678cf.png]

## 3 题目提示 ##

数中节点数在 \[1, 5000\] 范围内  
1 <= Node.val <= 10^7  
root 是二叉搜索树  
1 <= val <= 10^7

## 4 思路 ##

方法一：递归  
二叉搜索树满足如下性质:

*  左子树所有节点的元素值均小于根的元素值;
 *  右子树所有节点的元素值均大于根的元素值。  
    据此可以得到如下算法:
 *  若root为空则返回空节点;
 *  若val = root.val，则返回root;
 *  若val < root.val，递归左子树;
 *  若val > root.val，递归右子树。

复杂度分析

*  时间复杂度:O(N)，其中N是二叉搜索树的节点数。最坏情况下二叉搜索树是—条链，且要找的元素比链末尾的元素值还要小(大），这种情况下我们需要递归N次
 *  空间复杂度:O(N)。最坏情况下递归需要O(N)的栈空间。

方法二：迭代  
我们将方法—的递归改成迭代写法:

*  若root为空则跳出循环，并返回空节点;
 *  若val= root.val，则返回root;
 *  若val <root.val，将root置为root.left;
 *  若val > root.val，将root置为root.right。

复杂度分析

*  时间复杂度:O(N)，其中N是二叉搜索树的节点数。最坏情况下二叉搜索树是—条链，且要找的元素比链末尾的元素值还要小(大)，这种情况下我们需要迭代Ⅳ次
 *  空间复杂度:O(1)。没有使用额外的空间。

## 5 我的答案 ##

递归：

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

迭代：

class Solution {
        
        public TreeNode searchBST(TreeNode root, int val) {
        
            while (root != null) {
        
                if (val == root.val) {
        
                    return root;
                }
                root = val < root.val ? root.left : root.right;
            }
            return null;
        }
    }

[53537f18afbd4933a098fac6e4df578f.png]: https://img-blog.csdnimg.cn/53537f18afbd4933a098fac6e4df578f.png
[199e3fa3a5b0418697bf67744cf678cf.png]: https://img-blog.csdnimg.cn/199e3fa3a5b0418697bf67744cf678cf.png