这道题其实跟第530题是一样的。都是求二叉搜索树的任意两个结点之差的最小值。这时候关键要清楚二叉搜索树的原理,即当前节点大于其左子树小于其右子树。同时考虑到二叉搜索树的中序遍历实际上一个正序排序的过程,因此可以先对二叉搜索树中序遍历并保存到list中,然后循环比较前后两个元素之差找到最小差即可。
public int minDiffInBST(TreeNode root) { ArrayList<Integer> list = new ArrayList<Integer>(); help(root,list); Object[] arr = list.toArray(); int res = Integer.MAX_VALUE; for(int i=1;i<arr.length;i++){ res = ((Integer)arr[i] - (Integer)arr[i-1])<res?((Integer)arr[i] - (Integer)arr[i-1]):res; } return res; } public void help(TreeNode root,ArrayList<Integer> list){ if(root == null){ return; } help(root.left,list); list.add(root.val); help(root.right,list); }
这道题其实跟第530题是一样的。都是求二叉搜索树的任意两个结点之差的最小值。这时候关键要清楚二叉搜索树的原理,即当前节点大于其左子树小于其右子树。因此,如果某一个结点(假设为temp)与另一个结点(假设为next)的差值最小,那么next要么是temp的左子树的最大值,要么是temp的右子树的最小值,也就是要么在temp的左子树的最右边,要么在temp的右子树的最左边。这样就可以遍历每一个结点,并求出其最小差。
public int minDiffInBST(TreeNode root) { if(root == null || (root.left == null && root.right == null)) return Integer.MAX_VALUE; int temp = root.val; int leftMax = temp; int rightMin = temp; //左子树 TreeNode leftTree = root.left; //右子树 TreeNode rightTree = root.right; //寻找左子树的最大值 while(leftTree != null){ leftMax = leftTree.val; leftTree = leftTree.right; } //寻找右子树的最小值 while(rightTree != null){ rightMin = rightTree.val; rightTree = rightTree.left; } if(root.left == null){ int res = rightMin - temp; return Math.min(res,minDiffInBST(root.right)); } if(root.right == null){ int res = temp - leftMax; return Math.min(res,minDiffInBST(root.left)); } int res = (temp - leftMax) < (rightMin - temp)?(temp - leftMax):(rightMin - temp); int left = minDiffInBST(root.left); int right = minDiffInBST(root.right); return Math.min(res,Math.min(left,right)); }
第二种方法要比第一种效率高,但第一种写起来简单。