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.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ 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); } } }
Iterative solution:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int closestValue(TreeNode root, double target) { if (root == null) { throw new NullPointerException("Tree must be non-empty"); } int result = 0; double gap = Double.MAX_VALUE; while (root != null) { if (root.val == target) { return root.val; } double dist = Math.abs(root.val - target); if (dist < gap) { result = root.val; gap = dist; } if (target > root.val) { root = root.right; } else if (target < root.val) { root = root.left; } } return result; } }
No comments:
Post a Comment