LeetCode783题：二叉搜索树结点最小距离

思路一：中序遍历然后循环比较

这道题其实跟第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));
    }

总结：

第二种方法要比第一种效率高，但第一种写起来简单。