270. Closest Binary Search Tree Value

iteration, 左右走去找到 upper, lower, 最後比較差值

time: O(h), tree height

space: O(1)

可以參考這個

https://www.jiuzhang.com/problem/closest-binary-search-tree-value/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int closestValue(TreeNode root, double target) {
        
        TreeNode upper = root;
        TreeNode lower = root;
        while (root != null) {
            if (root.val > target) {
                upper = root;
                root = root.left;
            } else if (root.val < target) {
                lower = root;
                root = root.right;
            } else {
                return root.val;
            }
        }
        if (Math.abs(upper.val - target) > Math.abs(target - lower.val)) {
            return lower.val;
        }
        return upper.val;
    }
}

更精簡的

class Solution {
  public int closestValue(TreeNode root, double target) {
    int val;
    int closest = root.val;
    while(root != null) {
      val = root.val;
      closest = Math.abs(val - target) > Math.abs(closest - target) ? closest : val;
      root = root.val < target ? root.right: root.left;
    }
    
    return closest;
  }
}