LeetCode 270 - Closest Binary Search Tree Value

http://buttercola.blogspot.com/2015/09/leetcode-closest-binary-search-tree.html
Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.
Note:
Given target value is a floating point.
You are guaranteed to have only one unique value in the BST that is closest to the target.

X.
https://discuss.leetcode.com/topic/30159/super-clean-recursive-java-solution

    public int closestValue(TreeNode root, double target) {
        return closest(root, target, root.val);
    }
    
    private int closest(TreeNode node, double target, int val) {
        if (node == null) return val;
        if (Math.abs(node.val - target) < Math.abs(val - target)) val = node.val;
        if (node.val < target) val = closest(node.right, target, val);
        else if (node.val > target) val = closest(node.left, target, val);
        return val;
    }

http://segmentfault.com/a/1190000003797291
https://discuss.leetcode.com/topic/22590/4-7-lines-recursive-iterative-ruby-c-java-python

根据二叉树的性质，我们知道当遍历到某个根节点时，最近的那个节点要么是在子树里面，要么就是根节点本身。所以我们根据这个递归，返回子树中最近的节点，和根节点中更近的那个就行了。

    public int closestValue(TreeNode root, double target) {
        // 选出子树的根节点
        TreeNode kid = target < root.val ? root.left : root.right;
        // 如果没有子树，也就是递归到底时，直接返回当前节点值
        if(kid == null) return root.val;
        // 找出子树中最近的那个节点
        int closest = closestValue(kid, target);
        // 返回根节点和子树最近节点中，更近的那个节点
        return Math.abs(root.val - target) < Math.abs(closest - target) ? root.val : closest;
    }

public class Solution {

    private double min = Double.MAX_VALUE;

    private int ans = 0;

    public int closestValue(TreeNode root, double target) {

        if (root == null) {

            return Integer.MAX_VALUE;

        }

         

        closestValueHelper(root, target);

         

        return ans;

    }

     

    private void closestValueHelper(TreeNode root, double target) {

        if (root == null) {

            return;

        }

         

        if (Math.abs((double) root.val - target) < min) {

            min = Math.abs((double) root.val - target);

            ans = root.val;

        }

         

        if (root.val > target) {

            closestValueHelper(root.left, target);

        } else if (root.val < target) {

            closestValueHelper(root.right, target);

        }

    }

}

http://www.chenguanghe.com/closest-binary-search-tree-value/

X. Iterative
https://discuss.leetcode.com/topic/22588/java-iterative-solution

Avoid using Integer.MAX_VALUE because it does not work for the case [2147483647], 0.0.

I think the else statement could make the program faster when we have a very tall tree, because it stops immediately instead of iterating till the leaf.

public int closestValue(TreeNode root, double target) {
    double closest = Integer.MAX_VALUE;
    int value = 0;
    TreeNode current = root;
    while (current != null) {
        if (closest > Math.abs(current.val-target)) {
            closest = Math.abs(current.val-target);
            value = current.val;
        }
        
        if (current.val < target) {
            current = current.right;
        } else if (current.val > target) {
            current = current.left;
        } else {
            break;
        }
    }
    return value;
}

https://discuss.leetcode.com/topic/25219/clean-and-concise-java-solution
http://segmentfault.com/a/1190000003797291

    public int closestValue(TreeNode root, double target) {
        int closest = root.val;//\\
        while(root != null){
            // 如果该节点的离目标更近，则更新到目前为止的最近值
            closest = Math.abs(closest - target) < Math.abs(root.val - target) ? closest : root.val;
            // 二叉搜索
            root = target < root.val ? root.left : root.right;
        }
        return closest;
    }

LIKE CODING: LeetCode [270] Closest Binary Search Tree Value

    int closestValue(TreeNode* root, double target) {

        int ret = root->val;

        closestValue(root, target, ret);

        return ret;

    }

    void closestValue(TreeNode* root, double target, int &ret){

        if(root){

//            if(target == (double)(root->val)) {ret = target; return;}

            if(abs(root->val - target)<abs(ret - target))

                ret = root->val;

            if(target<(double)root->val)

                closestValue(root->left, target, ret);

            else

                closestValue(root->right, target, ret);

        }

    }

Closest Binary Tree Value

 3     int closestValue(TreeNode* root, double target) {
 4         if (!root) return INT_MAX;
 5         if (!(root -> left) && !(root -> right)) return root -> val;
 6         int left = closestValue(root -> left, target);
 7         int right = closestValue(root -> right, target);
 8         double td = abs(root -> val - target), ld = abs(left - target), rd = abs(right - target);
 9         if (td < ld) return td < rd ? root -> val : right;
10         else return ld < rd ? left : right;
11     }

http://www.cnblogs.com/airwindow/p/4799802.html
问了了下时空复杂度 时间复杂度我讲了了⼀一下如果树极度不不平衡会退化成
O(n)
变种：第⼀一题给了了⼀一个bst和⼀一个（lower, higher），求在这个range⾥里里⾯面
的所有node的和。⽐比较直接