MinimumAbsoluteDifferenceInBSTOPT [source code]

public class MinimumAbsoluteDifferenceInBSTOPT {
    int diff = Integer.MAX_VALUE;
    int prev = Integer.MAX_VALUE;

    public void inorderPass(TreeNode root) {
        if (root == null) {
            return;
        }
        inorderPass(root.left);
        diff = Math.min(diff, prev - root.val);       //no need to use Math.abs here
        prev = root.val;
        inorderPass(root.right);
    }

    public int getMinimumDifference(TreeNode root) {
        inorderPass(root);
        return diff;
    }
}

这个是 submission 最优解,16ms;

这个答案比我的答案快的一个原因, 也是一个算法加速的典型原因了, 就是我的算法是一个 overkill;
我输出了整个完整的in order traversal, 而且后面还做了一个完整的 sort.

其实单单是这个题目, 用类似 DP, 或者 recursion 的思路来做就行了. 前面也说过了, BST 的问题, 很多时候真的是一个 recursion 就解决了;

这个是另外一个 submission 最优解, 同是也是 discussion 最优解; 以下是作者的讲解:

The most common idea is to first inOrder traverse the tree and compare the delta between each of the adjacent values. It's guaranteed to have the correct answer because it is a BST thus inOrder traversal values are sorted.

Solution 1 - In-Order traverse, time complexity O(N), space complexity O(1).

public class Solution {  
    int min = Integer.MAX_VALUE;  
    Integer prev = null;  

    public int getMinimumDifference(TreeNode root) {  
        if (root == null) return min;  

        getMinimumDifference(root.left);  

        if (prev != null) {  
            min = Math.min(min, root.val - prev);  
        }  
        prev = root.val;  

        getMinimumDifference(root.right);  

        return min;  
    }  

}

还是不太看得懂这个算法; 感觉这里介绍的好像是一个 general 的pairwise in BST的技术?

其实这里完成的不是pairwise. 我之前自己的算法有问题的主要原因, 是因为我其实 sort 了两次. 我刚才改了一下, 把traversal之后的

Arrays.sort(ar);

删除了之后, 我的答案直接也是最优解了, 16ms;

这里之所以只维护一个 prev 就行了, 就是因为知道我们 traversal 的顺序是一个 sorted order的, 所以只要保留一个 prev 就行了: we don't compare every pair, but only between adjacent numbers (as adjacent in an inorder list);

他们的这个算法就是比我的节省了 space, 这个也是显而易见的, 因为这个问题最后求的就是一个 min 问题, min 问题不需要维护额外 space 这个应该是常识了;

注意的一点是这个算法里面:

        inorderPass(root.left);  
        diff = Math.min(diff, prev - root.val);       //no need to use Math.abs here  
        prev = root.val;  
        inorderPass(root.right);

这几行的顺序一点都不能错;

如果非要用 invariant 的观点来理解, 可以认为 invariant 是: after returning from each subtree(or its root), the prev points to the largest node in this subtree. 在理解的时候要注意上面四行的顺序, 以及如果 visit 的是(val, null, null)这样的 leaf, 实际上也是会触发 prev 的更新的;

另外这个问题上面的作者还有一个 followup:

What if it is not a BST? (Follow up of the problem) The idea is to put values in a TreeSet and then every time we can use O(lgN) time to lookup for the nearest values.

Solution 2 - Pre-Order traverse, time complexity O(NlgN), space complexity O(N).

public class Solution {  
    TreeSet<Integer> set = new TreeSet<>();  
    int min = Integer.MAX_VALUE;  

    public int getMinimumDifference(TreeNode root) {  
        if (root == null) return min;  

        if (!set.isEmpty()) {  
            if (set.floor(root.val) != null) {  
                min = Math.min(min, root.val - set.floor(root.val));  
            }  
            if (set.ceiling(root.val) != null) {  
                min = Math.min(min, set.ceiling(root.val) - root.val);  
            }  
        }  

        set.add(root.val);  

        getMinimumDifference(root.left);  
        getMinimumDifference(root.right);  

        return min;  
    }  
}

这个代码其实也不难, 只要inductively assume set 一直是sorted 的就行了. 评论里面给出了另外一种思路, 就是先直接一个inorder traversal把所有的 val 全都collect, 然后一个 sort, 然后过一遍1pass 就行了, 就跟我之前自己的代码的时候那样写就行了;

题外话, 关于思考这个问题的时候, 首先, 还是从简单的例子开始, 比如从一个只有三层的例子. 在这个例子思考的时候, prev 这个指针可以用一个比如假想的红点来表示;

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