WE ARE HIRING! Software engineer interviewers from Amazon, Facebook and Twitter. Please email baozitraining@outlook.com if you are interested
New leetcode solution video on YouTube.com/baozitraining
Leetcode solution 270: Closest Binary Search Tree Value
https://blog.baozitraining.org/2019/04/leetcode-solution-270-closest-binary.html
https://youtu.be/GcrvRcEM9Hs
Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.
Note:
Example:
Input: root = [4,2,5,1,3], target = 3.714286
4
/ \
2 5
/ \
1 3
Output: 4
Problem link
You can find the detailed video tutorial here
This is a very easy problem as long as you are familiar with Binary Search Tree. In order to find the value that is closest to the given target, we can traverse the tree and keep a record of the minimum delta. Of course we can traverse the entire tree but we can definite do it better by always branch out either left or right given the target and root node value. For example, if current node is 10, and target is 9, the next possible smaller value must exist only on the left part of or with the current node
10
/ \
7 11
private double curMinDelta = Double.MAX_VALUE; | |
---|---|
private int smallestValue = 0; | |
public int closestValue(TreeNode root, double target) { | |
this.searchMin(root, target); | |
return this.smallestValue; | |
} | |
private void searchMin(TreeNode root, double target) { | |
if (root == null) { | |
return; | |
} | |
if (target == root.val) { | |
this.smallestValue = root.val; | |
return; | |
} | |
double delta = Math.abs(target - root.val); | |
if (delta < this.curMinDelta) { | |
smallestValue = root.val; | |
this.curMinDelta = delta; | |
} | |
if (target < root.val) { | |
this.searchMin(root.left, target); | |
} else { | |
this.searchMin(root.right, target); | |
} | |
} |
view rawCloestBinarySearchTreeValue.java hosted with ❤ by GitHub
Time Complexity: assuming tree size is N,O(lgN) since we are doing binary search Space Complexity:O(1) if not considering recursion function stacks.
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;
}
Time Complexity: assuming tree size is N,O(lgN) since we are doing binary search Space Complexity:O(1)