MinimumAbsoluteDifferenceInBST [source code]

public class MinimumAbsoluteDifferenceInBST {
    private List<Integer> inOrderTraversal = new ArrayList<>();

    public int getMinimumDifference(TreeNode root) { 
        go(root);
        int min = Integer.MAX_VALUE;
        Integer[] ar = inOrderTraversal.toArray(new Integer[0]);
        // Arrays.sort(ar);         // This is not needed any more!
        for (int i = 1; i < ar.length; i++) {
            if (ar[i] - ar[i - 1] < min) min = ar[i] - ar[i - 1];
        }
        return min; 
    }

    public void go(TreeNode root) {
        if (root == null) return;
        go(root.left);
        inOrderTraversal.add(root.val);
        go(root.right);
    }
}

算法本身的思路是非常简单的, 直接先一个in order traversal做一个 list 出来, 然后有了这个 list,
照最小绝对值的差值就不难找了. 我这里的做法是先 sort 然后直接过一个1pass 就行了;

注意这一行:

        Integer[] ar = inOrderTraversal.toArray(new Integer[0]);

这里的两个 Integer 都必须是 Integer, 不能是 int. 具体的原因我也不是很清楚, 好像这个toArray()
函数就是这个特性;

速度是22ms, 26%, 不算很好;

Problem Description

Given a binary search tree with non-negative values, find the minimum absolute difference
between values of any two nodes.

Example:

Input:

1
\
3
/
2

Output:
1

Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between
2 and 3).
Note: There are at least two nodes in this BST.

Difficulty:Easy
Category:Algorithms
Acceptance:47.04%
Contributors:
nagasupreeth
Topics:
Binary Search Tree
You might like:
(E) K-diff Pairs in an Array
Company:
Google