In a binary search tree, find the node containing the closest number to the given target number.

Assumptions:

• The given root is not null.
• There are no duplicate keys in the binary search tree.

Examples:

5

/ \

2 11

 /    \

6     14

closest number to 4 is 5

closest number to 10 is 11

closest number to 6 is 6

Solution: 每次移动root时，跟global closest比较并更新

  public int closest(TreeNode root, int target) {
    int temp = Integer.MIN_VALUE;
    while (root != null) {
      if (root.key == target) {
        return target;
      } else if (root.key < target) {
        temp = (temp == Integer.MIN_VALUE || Math.abs(temp - target) > Math.abs(root.key - target))
                  ? root.key : temp;
        root = root.right;
      } else {
        temp = (temp == Integer.MIN_VALUE || Math.abs(temp - target) > Math.abs(root.key - target))
                  ? root.key : temp;
        root = root.left;
      }
    }
    return temp;
  }