270. Closest Binary Search Tree Value

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.

思路:用的pre-order travseral来做的,需要用一个global mindiff来找到target跟节点的最小差值,然后把此节点赋给closet.

public class Solution {
    public int closestValue(TreeNode root, double target) {
        int closet = root.val;
        double mindiff = Double.MAX_VALUE;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        while(!stack.isEmpty() || current != null) {
            if (current != null) {
                stack.push(current);
                double diff = Math.abs(target - current.val);
                if (diff < mindiff) {
                    mindiff = diff;
                    closet = current.val;
                }
                current = current.left;
            } else {
                current = stack.pop();
                current = current.right;
            }
        }

        return closet;
    }
}

二分, 递归

public class Solution {
    public int closestValue(TreeNode root, double target) {
        int closet = root.val;
        while(root != null) {
            // 更新到离目标节点的最近值
            closet = Math.abs(closet - target) > Math.abs(root.val - target) ? root.val : closet;
            root = target < root.val ? root.left : root.right; // 二分,找所在节点
        }
        return closet;
    }
}

Reference: https://segmentfault.com/a/1190000003797291

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s