“This is the 26th day of my participation in the November Gwen Challenge. See details of the event: The Last Gwen Challenge 2021”.

Topic describes

This is a search in the 700. binary search tree on LeetCode, the difficulty is simple.

Tag: “Tree search”, “iteration”, “recursion”

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 and the values: 2Copy the code

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.

recursive

According to the meaning of the question, “recursive” search can be carried out.

Code:

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) return root;
        returnroot.val < val ? searchBST(root.right, val) : searchBST(root.left, val); }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n), ignoring the extra space overhead caused by recursion

The iteration

Similarly, you can use “iteration” to search.

Code:

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while(root ! =null&& root.val ! = val) { root = root.val < val ? root.right : root.left; }returnroot; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

The last

This is the 700th article in our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 questions in LeetCode as of the start date, some of which have locks. We will finish all the questions without locks first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.