LeetCode - Easy - 700. Search in a Binary Search Tree-蒲公英云

LeetCode - Easy - 700. Search in a Binary Search Tree

Topic

Tree

Description

https://leetcode.com/problems/search-in-a-binary-search-tree/

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node’s value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

Example 1:

Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]

Example 2:

Input: root = [4,2,7,1,3], val = 5
Output: []

Constraints:

The number of nodes in the tree is in the range [ 1 , 5000 ] [1, 5000] [1,5000].
1 < = N o d e . v a l < = 1 0 7 1 <= Node.val <= 10^7 1<=Node.val<=107
root is a binary search tree.
1 < = v a l < = 1 0 7 1 <= val <= 10^7 1<=val<=107

Analysis

方法一：递归法

方法二：迭代法

Submission

import com.lun.util.BinaryTree.TreeNode;
public class SearchInABinarySearchTree { 
    //方法一：递归法
    public TreeNode searchBST(TreeNode root, int val) { 
        if(root == null) return null;
        if(val < root.val)
            return searchBST(root.left, val);
        else if(root.val < val)
            return searchBST(root.right, val);
        else 
            return root;
    }
    //方法二：迭代法
    public TreeNode searchBST2(TreeNode root, int val) { 
        TreeNode p = root;
        while(p != null) { 
            if(val < p.val) { 
                p = p.left;
            }else if(val > p.val){ 
                p = p.right;
            }else { 
                return p;
            }
        }
        return null;
    } 
}

Test

import static org.junit.Assert.*;
import org.junit.Test;
import com.lun.util.BinaryTree;
import com.lun.util.BinaryTree.TreeNode;
public class SearchInABinarySearchTreeTest { 
    @Test
    public void test() { 
        SearchInABinarySearchTree obj = new SearchInABinarySearchTree();
        TreeNode root = BinaryTree.integers2BinaryTree(4,2,7,1,3);
        TreeNode expected = BinaryTree.integers2BinaryTree(2,1,3);
        assertTrue(BinaryTree.equals(obj.searchBST(root, 2), expected));
        assertNull(obj.searchBST(root, 5));
    }
    @Test
    public void test2() { 
        SearchInABinarySearchTree obj = new SearchInABinarySearchTree();
        TreeNode root = BinaryTree.integers2BinaryTree(4,2,7,1,3);
        TreeNode expected = BinaryTree.integers2BinaryTree(2,1,3);
        assertTrue(BinaryTree.equals(obj.searchBST2(root, 2), expected));
        assertNull(obj.searchBST2(root, 5));
    }
}