Massive Algorithms: LeetCode 530

https://leetcode.com/problems/minimum-absolute-difference-in-bst

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.

X. Inorder travsere
https://discuss.leetcode.com/topic/80796/java-o-n-time-inorder-traversal-solution

Since this is a BST, the inorder traversal of its nodes results in a sorted list of values. Thus, the minimum absolute difference must occur in any adjacently traversed nodes. I use the global variable "prev" to keep track of each node's inorder predecessor.

    int minDiff = Integer.MAX_VALUE;
    TreeNode prev;
    
    public int getMinimumDifference(TreeNode root) {
        inorder(root);
        return minDiff;
    }
    
    public void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        if (prev != null) minDiff = Math.min(minDiff, root.val - prev.val);
        prev = root;
        inorder(root.right);
    }

Indeed, hijacking a mutable array to emulate pass-by-reference reeks of a recovering C++ programmer (guilty as charged ;) )

class WrapInt{
    int value;
}

    public int getMinimumDifference(TreeNode root) {
     List<Integer> prev = new ArrayList<>(); // contains at most 1 value
     int[] min = new int[]{Integer.MAX_VALUE};
     inorder(root, prev, min);
     return min[0];
    }
    
    private void inorder(TreeNode root, List<Integer> prev, int[] min) {
     if (root == null) return;
     
     inorder(root.left, prev, min);
     if (prev.isEmpty()) {
      prev.add(root.val);
     } else {
      min[0] = Math.min(min[0], Math.abs(root.val - prev.get(0)));
      prev.set(0, root.val);
     }
     inorder(root.right, prev, min);     
    }

https://discuss.leetcode.com/topic/80823/twof-solutions-in-order-traversal-and-a-more-general-way-using-treeset

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

Could you explain using Integer.MAX_VALUE;

int min = Integer.MAX_VALUE;

That's just for initializing the return value. Because when you call

min = Math.min(min, Math.abs(root.val - set.floor(root.val)));

the first time, you want min to be whatever the right part is, which can be achieved by setting min to have the maximum possible value.

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;
    }
    
}

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).

    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, Math.abs(root.val - set.floor(root.val)));
            }
            if (set.ceiling(root.val) != null) {
                min = Math.min(min, Math.abs(root.val - set.ceiling(root.val)));
            }
        }
        
        set.add(root.val);
        
        getMinimumDifference(root.left);
        getMinimumDifference(root.right);
        
        return min;
    }

中序遍历BST得到的序列是有序序列。因此创建一个vector存储中序遍历的每一个节点就得到一个有序序列，然后遍历这个有序序列，在遍历过程中求出两两之差并更新最小的绝对值之差就能得到结果。
http://www.liuchuo.net/archives/3714

    int getMinimumDifference(TreeNode* root) {

        inOrder(root);

        int result = INT_MAX;

        for (int i = 1; i < tree.size(); i++)

            result = min(result, tree[i] - tree[i-1]);

        return result;

}

private:

    vector<int> tree;

    void inOrder(TreeNode* root) {

        if (root->left != NULL) inOrder(root->left);

        tree.push_back(root->val);

        if (root->right != NULL) inOrder(root->right); 

}

};

X. [lower, upper bound]
https://discuss.leetcode.com/topic/80916/java-no-in-order-traverse-solution-just-pass-upper-bound-and-lower-bound

It is just sort of property of the BST. Since the value of all the nodes of the left subtree is smaller than the current node, the value of the current node is the upper bound of the all the nodes in the left subtree. And for the right subtree, the value of the current node is the lower bound. You can draw a BST and have a look. If you draw a vertical line for 2 nodes, you will find all the nodes between those two lines are bounded by the value of the nodes which you draw the vertical lines.

Make use of the property of BST that value of nodes is bounded by their "previous" and "next" node.
Edit: Thanks to Stefan pointing out a small bug. Previous code would fail when testing [2147483647, 2147483646].
Now Long.MAX_VALUE/MIN_VALUE is used to mark the INF.

long minDiff = Long.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
    helper(root,Long.MIN_VALUE,Long.MAX_VALUE);
    return (int)minDiff;
}
private void helper(TreeNode curr, long lb, long rb){
    if(curr==null) return;
    if(lb!=Long.MIN_VALUE){
        minDiff = Math.min(minDiff,curr.val - lb);
    }
    if(rb!=Long.MAX_VALUE){
    minDiff = Math.min(minDiff,rb - curr.val);
    }
    helper(curr.left,lb,curr.val);
    helper(curr.right,curr.val,rb);
}

def getMinimumDifference(self, root):
    def mindiff(root, lo, hi):
        if not root:
            return float('inf')
        return min(root.val - lo,
                   hi - root.val,
                   mindiff(root.left, lo, root.val),
                   mindiff(root.right, root.val, hi))
    return mindiff(root, float('-inf'), float('inf'))

X.
https://leetcode.com/problems/minimum-absolute-difference-in-bst/discuss/99905/Two-Solutions-in-order-traversal-and-a-more-general-way-using-TreeSet

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;
    }
}

LeetCode 530 - Minimum Absolute Difference in BST

Labels

Popular Posts