Two ways of Solving in Java using recursion


  • 0
    L

    Way#1: Use the Inorder traversal and keep track of the previous node to maintain a global minimum. This beats 95% of the Java solutions.

    public class Solution {
      private int globalMin = Integer.MAX_VALUE;
      private TreeNode prev;
        
      public int getMinimumDifference(TreeNode root)
      {
        helper(root);
        return globalMin;
      }
    
      private void helper(TreeNode root)
      {
        if (root == null)
        {
          return;
        }
        helper(root.left);
        if (prev != null)
        {
          globalMin = Math.min(globalMin, Math.abs(root.val - prev.val));
        }
        prev = root;
        helper(root.right);
      }
    }
    

    Way#2: It includes a general pattern that may be used in different problems as well. The idea is to return both min and max values for each traversal. The min is picked up from the differences between root2left, root2right, root2leftmax and root2rightmin.

     public int getMinimumDifference(TreeNode root){
          Wrapper wrapper = helper(root);
        if (wrapper == null)
        {
          return 0;
        }
        return (int) wrapper.diff;
     }
     
      private Wrapper helper(TreeNode root)
      {
        if (root == null)
        {
          return null;
        }
        Wrapper left = helper(root.left);
        Wrapper right = helper(root.right);
        long root2left = root.left == null ? Long.MAX_VALUE
            : Math.abs(root.val - root.left.val);
        long right2root = root.right == null ? Long.MAX_VALUE
            : Math.abs(root.right.val - root.val);
        long min = Math.min(root2left, right2root);
        if (left != null)
        {
          min = Math.min(Math.min(min, left.diff),
              Math.abs(root.val - left.max));
        }
        if (right != null)
        {
          min = Math.min(Math.min(min, right.diff),
              Math.abs(right.min - root.val));
        }
        return new Wrapper(left == null ? root.val : left.min,
            right == null ? root.val : right.max, min);
      }
    
      private class Wrapper
      {
        long min;
    
        long max;
    
        long diff;
    
    
    
        Wrapper(long min, long max, long diff)
        {
          this.min = min;
          this.max = max;
          this.diff = diff;
        }
      }
    

Log in to reply
 

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