LeetCode.700.Search in a Binary Search Tree 在BST中搜索

题目描述

700 Search in a Binary Search Tree https://leetcode-cn.com/problems/search-in-a-binary-search-tree/

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node's value equals the given value. Return the subtree rooted with that node. If such node doesn't exist, you should return NULL.

For example, 

Given the tree:
        4
       / \
      2   7
     / \
    1   3

And the value to search: 2
You should return this subtree:

      2
     / \
    1   3

In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL.

Note that an empty tree is represented by NULL, therefore you would see the expected output (serialized tree format) as [], not null.

解题过程

在二叉搜索树BST中搜索，也就是二分搜索。 时间复杂度 O(logn)，空间复杂度 O(1)

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

GitHub代码

algorithms/leetcode/leetcode/_700_SearchBinarySearchTree.java https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_700_SearchBinarySearchTree.java