LeetCode（Tree)700. Search in a Binary Search Tree

刺骨的言语ヽ痛彻心扉 2023-09-26 20:16 22阅读 0赞

# 1.问题 #

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node’s value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

Example 1:  
![在这里插入图片描述][e43528c902ef482f6c3d7e7127f02fba.jpeg_pic_center]

> Input: root = \[4,2,7,1,3\], val = 2  
> Output: \[2,1,3\]

Example 2:  
![在这里插入图片描述][ac2cae12f8dc131ce47df9b8f793c994.jpeg_pic_center]

> Input: root = \[4,2,7,1,3\], val = 5  
> Output: \[\]

Constraints:

*  The number of nodes in the tree is in the range \[1, 5000\].
 *  1 <= Node.val <= 107
 *  root is a binary search tree.
 *  1 <= val <= 107

# 2. 解题思路 #

> `二叉搜索树是一种二叉树`，它满足以下性质：  
> 对于树中的任意节点，其`左子树中所有节点的值都小于该节点的值`。  
> 对于树中的任意节点，其`右子树中所有节点的值都大于该节点的值`。  
> 左右子树也分别为`二叉搜索树`。

## 方法1： ##

> 1.如果根节点为空或者根节点的值等于目标值，直接返回根节点，搜索结束。  
> 2.如果目标值小于根节点的值，说明目标值可能在左子树中，因为左子树中所有节点的值都小于根节点的值。因此，递归搜索左子树。  
> 3.否则，说明目标值可能在右子树中，因为右子树中所有节点的值都大于根节点的值。因此，递归搜索右子树。  
> `递归搜索的过程中，每次传递下去的参数是当前子树的根节点以及目标值。当搜索到目标节点时，直接返回该节点；否则，如果搜索到了空节点，说明目标值不在树中，返回null。`

# 3. 代码 #

## 代码1： ##

class Solution {
        
    	public TreeNode searchBST(TreeNode root, int val) {
        
    	    // 如果根节点为空或者根节点的值等于目标值，直接返回根节点
    	    if (root == null || root.val == val) {
        
    	        return root;
    	    }
    	    // 如果目标值小于根节点的值，递归搜索左子树
    	    if (val < root.val) {
        
    	        return searchBST(root.left, val);
    	    }
    	    // 否则，递归搜索右子树
    	    return searchBST(root.right, val);
    	}
    }

> 解题思路基本相同

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

[e43528c902ef482f6c3d7e7127f02fba.jpeg_pic_center]: https://img-blog.csdnimg.cn/img_convert/e43528c902ef482f6c3d7e7127f02fba.jpeg#pic_center
[ac2cae12f8dc131ce47df9b8f793c994.jpeg_pic_center]: https://img-blog.csdnimg.cn/img_convert/ac2cae12f8dc131ce47df9b8f793c994.jpeg#pic_center