Minimum Absolute Difference in BST
给一个BST, 找其中的绝对值差最小的两个数, 并且返回差值. 这个题因为是bst,所以可以直接转化成排序数组, 然后再做, 讨论有一个解法如下, 是利用边界逐渐靠拢绝对值的方法. 很巧妙.
public class Solution {
int minDiff = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
helper(root,Integer.MIN_VALUE,Integer.MAX_VALUE);
return minDiff;
}
private void helper(TreeNode curr, int lb, int rb){
if(curr==null) return;
if(lb!=Integer.MIN_VALUE){
minDiff = Math.min(minDiff,curr.val - lb);
}
if(rb!=Integer.MAX_VALUE){
minDiff = Math.min(minDiff,rb - curr.val);
}
helper(curr.left,lb,curr.val);
helper(curr.right,curr.val,rb);
}
}