Easy
這道題mock的時候沒做出來，老師說這種送分題應(yīng)該是幾分鐘就寫好的，我汗。

recursive way

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int closestValue(TreeNode root, double target) {
        int a = root.val;
        TreeNode child = a > target ? root.left : root.right;
        if (child == null){
            return root.val;            
        }
        int b = closestValue(child, target);
        if (Math.abs(a - target) < Math.abs(b - target)){
            return root.val;
        } else {
            return b;
        }
    }
}

recursion寫出來跑得挺慢的，才打敗4%, 試了一下iterative way,提高到20%左右。下面這個寫法最簡潔，不過后面的寫法更加human一點

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

Iterative比較human跟intuitive的寫法：思路很代碼一樣都很straightforward，先keep一個變量minDiff表示最小跟target的差距，然后以root跟target的差initialize. 再看root跟target哪個大，如果target大，就繼續(xù)看right subtree. 反之則看左子樹。這樣最后traverse完整棵樹的高度而并非每棵樹的節(jié)點，所有用logN.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int closestValue(TreeNode root, double target) {
        int minDiffVal = root.val;
        double minDiff = Math.abs(root.val - target);
        TreeNode curt = root;
        while (curt != null){
            if (Math.abs(curt.val - target) < minDiff){
                minDiff = Math.abs(curt.val - target);
                minDiffVal = curt.val;
            }
            curt = target > curt.val ? curt.right : curt.left;
        }
        return minDiffVal;
    }
}