Minimum Absolute Difference in BST
给一个BST, 找其中的绝对值差最小的两个数, 并且返回差值. 这个题因为是bst,所以可以直接转化成排序数组, 然后再做, 讨论有一个解法如下, 是利用边界逐渐靠拢绝对值的方法. 很巧妙.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
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); } } |