Java DFS Solution without Sorting


  • 0

    In this problem, the minimum absolute difference is Math.min(max value from left, min value from right)

    We follow a bottom-up approach where we let every node return an array of values of size 2.

    The first index has min value obtained till now and 2nd has max value.

    We calculate this for a particular node and calculate min and max values for its parent.

    public class Solution {
        
        public int getMinimumDifference(TreeNode root) 
        {
            if(root == null || (root.left == null && root.right == null))
                return 0;
                
            TreeNode dummy = new TreeNode(Integer.MAX_VALUE);
            helper(root,dummy);
            
            return dummy.val;
        }
        
        public int[] helper(TreeNode root,TreeNode dummy)
        {
            if(root.left == null && root.right == null)
            {
                return new int[]{root.val,root.val};
            }
            
            int[] left  = new int[2];
            int[] right = new int[2];
            
            if(root.left != null)
            {
                left = helper(root.left,dummy);
            }
            
            if(root.right != null)
            {
                right = helper(root.right,dummy);
            }
            
            if(root.left == null)
            {
                left = right;
            }
            
            if(root.right == null)
            {
                right = left;
            }
    
            dummy.val = Math.min(dummy.val,Math.abs(root.val-left[1]));
            dummy.val = Math.min(dummy.val,Math.abs(root.val-right[0]));
            
            int min_val = Math.min(Math.min(left[0],right[0]),root.val);
            int max_val = Math.max(Math.max(left[1],right[1]),root.val);
            
            return new int[]{min_val,max_val};
        }
    }
    

Log in to reply
 

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