P67 二叉搜索树中查找数字

描述#

这个题目说的是，给你一棵二叉搜索树和一个数字，你要在二叉搜索树上找到这个数字，并返回它所在的节点。如果找不到这个数字，就返回空指针。

二叉搜索树的定义是：

左子树所有节点上的值都小于根节点上的值
右子树所有节点上的值都大于根节点上的值
左右子树同时也为二叉搜索树

比如说，给你的二叉搜索树是：
 8
/ \

2  16
/ 

1   4
给你的数字是 1。1 在这棵二叉搜索树里，因此你要返回节点 1。
如果给你的数字是 42，不在这棵树中，则返回空指针。

代码#

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  // Time: O(h), Space: O(h)
  public TreeNode searchBSTRecursive(TreeNode root, int val) {
    if (root == null || val == root.val) return root;
    else if (val < root.val) return searchBSTRecursive(root.left, val);
    else return searchBSTRecursive(root.right, val);
  }

  // Time: O(h), Space: O(1)
  public TreeNode searchBSTIterative(TreeNode root, int val) {
    while (root != null && val != root.val) {
      if (val < root.val) root = root.left;
      else root = root.right;
    }
    return root;
  }

}