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

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:
在这里插入图片描述

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

Example 2:
在这里插入图片描述

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);
    }
}