Binary tree -- 700. Search in binary search tree

1 Title Description

Given a binary search tree （BST） The root node root And an integer value val.

You need to BST The node value found in is equal to val The node of . Return the subtree with this node as the root . If the node doesn't exist , Then return to null .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/search-in-a-binary-search-tree

2 Title Example

3 Topic tips

The number of nodes in the number is [1, 5000] Within the scope of
1 <= Node.val <= 10^7
root It's a binary search tree
1 <= val <= 10^7

4 Ideas

Method 1 ： recursive
The binary search tree satisfies the following properties :

• The element values of all nodes in the left subtree are less than those of the root ;
• The element value of all nodes in the right subtree is greater than that of the root .
  The following algorithm can be obtained :
• if root If it is empty, an empty node will be returned ;
• if val = root.val, Then return to root;
• if val < root.val, Recursive left subtree ;
• if val > root.val, Recursive right subtree .

Complexity analysis

• Time complexity :O(N), among N Is the number of nodes in the binary search tree . In the worst case, the binary search tree is — Chain , And the element to be found is smaller than the element value at the end of the chain ( Big ）, In this case, we need recursion N Time
• Spatial complexity :O(N). In the worst case, recursion requires O(N) Stack space of .

Method 2 ： iteration
We're going to approach — The recursion of is changed into iterative writing :

• if root If it is empty, it will jump out of the cycle , And return an empty node ;
• if val= root.val, Then return to root;
• if val <root.val, take root Set as root.left;
• if val > root.val, take root Set as root.right.

Complexity analysis

• Time complexity :O(N), among N Is the number of nodes in the binary search tree . In the worst case, the binary search tree is — Chain , And the element to be found is smaller than the element value at the end of the chain ( Big ), In this case, we need to iterate Ⅳ Time
• Spatial complexity :O(1). No use of extra space .

5 My answer

recursive ：

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

iteration ：

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