题目描述

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node’s value equals the given value. Return the subtree rooted with that node. If such node doesn’t exist, you should return NULL.

In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL.

Note that an empty tree is represented by NULL, therefore you would see the expected output (serialized tree format) as [], not null.

方法思路

Approach1: recursive

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root == null) return root;
        if(val == root.val) return root;
        if(val < root.val)
            root = root.left;
        else
            root = root.right;
        
        return searchBST(root, val);
    }
}

Approach2: 将尾递归改为非递归的形式

class Solution{
    //Runtime: 1 ms, faster than 100.00%
    public TreeNode searchBST(TreeNode root, int val){
        if(root == null) return root;
        if(val == root.val) return root;
        while(root != null){
            if(val == root.val)
                return root;
            else if(val < root.val)
                 root = root.left;
            else
                root = root.right;
        }
        return null;
    }
}