ClosestBinarySearchTreeValueOPT [source code]

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

    public static void main(String[] args) {
        ClosestBinarySearchTreeValueOPT.Solution tester = new ClosestBinarySearchTreeValueOPT.Solution();
    }
}

这个跟前面那个 recursive 的算法是一个意思, 就是利用 BST 的性质, 缩小搜索空间; 只不过这里写的是一个 iterative 的版本;

其实我自己之前想了一个版本, 是:

public class Solution {  
    public int closestValue(TreeNode root, double target) {  
        if (root == null) return 0;  
        TreeNode originalRoot = root;  
        TreeNode parent = root;  
        TreeNode child = root;  
        while (child != null) {  
            parent = root;  
            root = child;  
            if (target == root.val) return root.val;  
            else if (target < root.val) child = root.left;  
            else child = root.right;  
        }  
        int res = Math.abs(parent.val - target) < Math.abs(root.val - target) ? parent.val : root.val;          
        return Math.abs(originalRoot.val - target) < Math.abs(res - target) ? originalRoot.val : res;  
    }  
}

认为只要比较最后两个 node 就行了, 但是这个想法是不对的, 最后被 break 的 Test Case 是:
[4,2,5,1,3]
3.714286
target 不一定会落在最后两个 node 之间的区间的, 比如这里的 target, 比1和3都大, 但是最后还是走到底了;
尝试修复这个逻辑, 加一个比较, 是最后两个node 之间的赢家跟最上面的 root 再来追加一个比较, 代码的变化反映在最后一行了; 不过这个逻辑还是不对:
[5,3,6,1,4,null,null,null,2]
2.857143
几个例子一看, 感觉还是要把整条 path 都比较一遍才能确定到底哪个是 closest;

Problem Description

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.
Difficulty:Easy
Category:Algorithms
Acceptance:39.16%
Contributor: LeetCode
Companies
microsoft google snapchat
Related Topics
tree binary search
Similar Questions
Count Complete Tree Nodes Closest Binary Search Tree Value II