My Java Solution using a helper class and a helper method


  • 0
    F

    The minimum difference of the tree should be the minimum difference on its left subtree, or the minimum difference on its right subtree, or the minimum value of root.val-(max of left subtree) and (min of right subtree)-root.val

    public class Solution {
        private static class RetVal {
            public int minDiff;
            public int min;
            public int max;
            
            public RetVal(int minDiff, int min, int max) {
                this.minDiff = minDiff;
                this.min = min;
                this.max = max;
            }
        }
        
        public int getMinimumDifference(TreeNode root) {
            RetVal res = getMinDiff(root);
            
            if(res == null) {
                return Integer.MAX_VALUE;
            } else {
                return res.minDiff;
            }
        }
        
        private RetVal getMinDiff(TreeNode node) {
            if(node == null) {
                return null;
            } else {
                RetVal left = getMinDiff(node.left), right = getMinDiff(node.right);
                boolean leftNil = left==null, rightNil = right==null;
    
                int curMinDiff = Math.min(leftNil?Integer.MAX_VALUE:Math.abs(node.val-left.max), rightNil?Integer.MAX_VALUE:Math.abs(node.val-right.min));
                int childMinDiff = Math.min(leftNil?Integer.MAX_VALUE:left.minDiff, rightNil?Integer.MAX_VALUE:right.minDiff);
                return new RetVal(Math.min(childMinDiff, curMinDiff), leftNil?node.val:left.min, rightNil?node.val:right.max);
            }
        }
    }
    

Log in to reply
 

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