“This is the first day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021”

The original link

700. Search in Binary Search Trees – LeetCode (leetcode-cn.com)

Topic describes

Given the root node of a binary search tree (BST) and a value. You need to find nodes in BST that have a value equal to the given value. Returns the subtree rooted with this node. If the node does not exist, NULL is returned.

The test case

Given the binary search tree: 4 / \ 2 7 / \ 1 3 and the values: 2 you should return such as the subtree: 2 / \ 1 3 in the example above, if the value we are looking for is 5, but since there are no nodes with a value of 5, we should return NULL.Copy the code

Parameter limits

There is no

Binary search tree features

Binary search tree (BST for short) is a binary tree. Each node has the following characteristics:

  • Greater than any node in the left subtree
  • Is less than any node in the right subtree

This is a binary search tree, and it marks the order in which it searches. And this order of traversal can also be called middle order traversal

Finding elements in a binary tree has the same performance as binary array lookup. Take finding a number 6:

Starting from root 5 -> larger than 5 -> compare with right node 7 of 5 -> smaller than 7 -> compare with left node 6 of 7 -> just foundCopy the code

Another example is finding a number 3:

Starting from root 5 -> smaller than 5 -> comparison of left node 2 with 5 -> comparison of left node 2 with 2 -> comparison of right node 4 with 2 -> comparison of left node with 4 -> no left node with 4 -> This tree has no 3 nodesCopy the code

Analysis of the

The specific search idea is the standard binary tree search idea

Binary tree traversal has a very strong recursive style, a relatively common traversal framework is as follows

function trave(root){
    // If there is logic to execute here, this is the prior traversal
    trave(root.left);
    // If there is logic to execute here, this is a middle-order traversal
    trave(root.right);
    // If there is logic to execute here, this is a back-order traversal
}
Copy the code

code

var searchBST = function(root, val) {
    let n = null;
    trave(root);
    return n;
    function trave(root){
        if(root == null) return;
        if(root.val>val){
            trave(root.left)
        }else if(root.val<val){
            trave(root.right)
        }else{ n = root; }}};Copy the code

Today’s force buckle brush problem share here, thank you for reading ~