Leetcode skimming: binary tree 20 (search in binary search tree)

700. Search in binary search tree

Force button topic address

Given a binary search tree （BST） And a value . You need to BST Found a node whose value is equal to the given value . Return the subtree with this node as the root . If the node doesn't exist , Then return to NULL.

for example ,

In the example above , If the value is 5, But because no node has a value of 5, We should go back to NULL.

 A very simple question . recursive , When the current node is empty , Returns an empty , The current node is larger than the target number , Check the left subtree , Otherwise, check the right subtree , If equal , Then return to . Because binary search tree is non decreasing . Orderly , The idea of dichotomy .

package com.programmercarl.tree;

/** * @ClassName SearchBST * @Descriotion TODO * @Author nitaotao * @Date 2022/7/5 21:17 * @Version 1.0 * https://leetcode.cn/problems/search-in-a-binary-search-tree/ * 700.  Search in binary search tree  **/
public class SearchBST {
    
    /** * BST, Also called balanced binary tree , It is a binary tree accessed by key , *  And it is required to keep the order , That is, any node is not less than its left offspring , Not greater than its right offspring （ Note that offspring , It's not a child ）. * BST The order of the ergodic sequence must be monotonic and non descending . * * @param root * @param val * @return */
    public TreeNode searchBST(TreeNode root, int val) {
    
        if (root == null) {
    
            return null;
        }
        if (root.val == val) {
    
            return root;
        } else if (root.val < val) {
    
            // The current value is smaller than the target value , Search on the right subtree 
            return searchBST(root.right, val);
        } else {
    
            // The current value is larger than the target value , Search on the left sub tree 
            return searchBST(root.left, val);
        }
    }
}