Java O(n) Easy To Read, Optimal Solution


  • 0
    B

    Explanation
    The idea to this question is to use a recursive approach to traverse through the tree, while propagating a Result object that helps us make calculations later on.

    Suppose we're considering any given node, n, in getMinimumDifferenceHelper(...).

    Firstly, we make recursive calls on n's left and right children. This gives us the propagated min, max, and minimum absolute difference of both left and right subtrees.

    Secondly, do we use an existing, propagated minimum absolute difference from the left or right subtree, or can we compute an even smaller value using n's value? We use the fact that n is a BST to see if we can compute an even smaller value involving n's value:

    /* To compute absolute difference values involving input n: */
    
    /* Left side absolute difference:  */ root.val - leftResult.max;
    /* Right side absolute difference: */ rightResult.min - root.val;
    

    Lastly, we update min, max, minimum absolute difference for n, package it into a Result object and return that.

    Time Complexity
    The time complexity is O(n) where n is the number of nodes in the tree rooted at input root, since we DFS through the tree to visit each node.

    class Solution {
        
       /* Records the min, max values, absDiff within a tree */ 
        class Result {
            int min;
            int max;
            int absDiff; // Minimum absolute difference
            Result(int minimum, int maximum, int abs) {
                min = minimum;
                max = maximum;
                absDiff = abs;
            }
        }
        
        /* Returns a Result object that contains the min, max, minimum absolute
         *   diff values within the tree root
         */
        public Result getMinimumDifferenceHelper(TreeNode root) {
            if (root == null) {
                return null;
            }
            Result leftResult = getMinimumDifferenceHelper(root.left);
            Result rightResult = getMinimumDifferenceHelper(root.right);
            
            // Initialize both left and right absolute values absurdly high
            int leftSideAbsDiff = Integer.MAX_VALUE;
            int rightSideAbsDiff = Integer.MAX_VALUE;
            
            // Compute the absolute difference involving the left subtree
            if (leftResult != null) {
                leftSideAbsDiff = Math.min(leftResult.absDiff, 
                                           root.val - leftResult.max);
            }
            // Compute the absolute difference involving the right subtree
            if (rightResult != null) {
                rightSideAbsDiff = Math.min(rightResult.absDiff, 
                                            rightResult.min - root.val);
            }
            // Compute all necessary data to return a new Result
            int min = leftResult != null ? leftResult.min : root.val;
            int max = rightResult != null ? rightResult.max : root.val;
            int absDiff = Math.min(leftSideAbsDiff, rightSideAbsDiff);
    
            return new Result(min, max, absDiff);
        }
        
        public int getMinimumDifference(TreeNode root) {
            Result result = getMinimumDifferenceHelper(root);
            return result.absDiff;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.