Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Leetcode700 – Binary search tree search

above

This article is the rookie brush problem record, only used as notes, not the best solution.

The title information

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.

For example,

Given a binary search tree:

    4
   / \
  2   7
 / \
1   3
Copy the code

And values: 2 you should return such as subtree:

  2     
 / \   
1   3
Copy the code

In the example above, if the value we are looking for is 5, but there are no nodes with a value of 5, we should return NULL.

Analysis of the solution idea:

Method 1:

So the first thing to do is to realize that this is a binary search tree. Binary search tree is mainly for left and right nodes, the left child node and its children are smaller than the root node, and the right child node and all children nodes are larger than the root node. So if you want to find the target element in the binary search tree, you can directly traverse the binary search tree. The target value is compared with each node, and the left and right recursive traversal is performed according to the size relationship between the target value and the node value until the target value is found. If the target value is not found at the end of the traversal, the value is considered not to exist in the binary search tree. Recurse in this way to get the desired result of the problem.

public TreeNode searchBST(TreeNode root, int val) { if(root == null){ return null; } if(root.val == val){ return root; }else if(root.val > val){ return searchBST(root.left,val); }else{ return searchBST(root.right,val); }}Copy the code

Complexity analysis

  • Time complexity O (n)
  • Space complexity O (1)

Afterword.

  • How many events through the ages? Leisurely. The Yangtze River is still rolling.