Java, Memorization, LRV


  • 0
    R

    Basic ideas are:
    Tilt = Math.abs(Left.Sum – Right.sum)
    WholeTreeTile = WholeTreeTilt(left) + Root.Tilt + WholeTreeTilt(right)
    Code as below:

    '''

        public class Solution {
           Map<TreeNode, Integer> sumMap;
           public int findTilt(TreeNode r) {
               if (r == null) return 0;
               else if (r.left == null && r.right == null) return r.val;sumMap = new HashMap<>();
               sumTotal(r);
               return findTiltHelper(r);
          }
    
    private int findTiltHelper(TreeNode r)
    {
        if (r == null) return 0;
        else if (r.left == null && r.right == null) return 0;
        int tilt = Math.abs(sumTotal(r.left) - sumTotal(r.right));
        return (findTiltHelper(r.left) + findTiltHelper(r.right) + tilt);
    }
    
    private int sumTotal(TreeNode n)
    {
        if (n == null) return 0;
        else if (sumMap.containsKey(n)) return sumMap.get(n);
        
        int l = sumTotal(n.left);
        int r = sumTotal(n.right);
        int v = l + r + n.val;
        sumMap.put(n, v);
        return v;
    }
    

    }''''


Log in to reply
 

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