Java solution with Global HashMap and Recursion


  • 0
    D

    The HashMap stores key as the nodes and value as the sum of the (left + right + node.val).

    Once all the nodes with respective keys is stored in the HashMap, calculate the tilt as:
    tile(curr) = |map.get(curr.left) - map.get(curr.right)|

    /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */

    public class Solution {
    private Map<TreeNode, Integer> map = new HashMap<>();
    public int findTilt(TreeNode root) {
    map.put(null, 0);
    constructMap(root);

        int sum = 0;
        for(TreeNode curr: map.keySet()) {
            if(curr == null) {
                continue;
            }
            sum += Math.abs(map.get(curr.left) - map.get(curr.right));
        }
        
        return sum;
    }
    
    private void constructMap(TreeNode root) {
        if(root == null) {
            return;
        }
        
        constructMap(root.left);
        constructMap(root.right);
        
        map.put(root, root.val + map.get(root.left) + map.get(root.right));
        return;
    }
    

    }


Log in to reply
 

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