AC JAVA one pass solution using HashMap


  • 0
    J

    The idea is to find the sum of each subtree from bottom to top. Using hashmap to store its sum. After traversing the entire tree, I check if any node's hash value has the half of the root's hash value. If so, return true. Note that if root's hash value is an odd number, then there is no way we can split the tree.

    class Solution {    
        public boolean checkEqualTree(TreeNode root) {
            if(root == null) return false;
            if(root != null && root.left == null && root.right == null) return false;
            Map<TreeNode, Integer> map = new HashMap<>();
            getSum(root, map);
            if(map.get(root) % 2 != 0) return false;
            return map.containsValue(map.get(root) / 2);
        }
        private void getSum(TreeNode root, Map<TreeNode, Integer> map){
            if(root == null) return;
            getSum(root.left, map);
            getSum(root.right, map);
            int sum = root.val;
            if(root.left != null) sum += map.get(root.left);
            if(root.right != null) sum += map.get(root.right);
            map.put(root, sum);
        }
    }
    

  • 1

    Great solution!
    Same idea here, but I use a set to store each subtree 'sum', and also I changed value of each node to 'sum'. Thus there's no need to hash each node to their 'sum's.


  • 1
    J

    @Candle309 thank you! yeah, your idea works too.


Log in to reply
 

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