Java code using HashMap, easy to understand


  • 0
    A
    class Solution {
    public boolean checkEqualTree(TreeNode root) {
        // algorithm 2017/08/20: record the sum of each subtree, and find whether there is a subtree-sum is the half of total
        if (null == root) {
            return false;
        }
        HashMap<TreeNode, Integer> subTreeSumMapping = new HashMap<>();
        int totalSum = calcSubTreeSum(root, subTreeSumMapping);
        if (1 == totalSum % 2) {
            return false;
        }
        
        for (Map.Entry<TreeNode, Integer> entry : subTreeSumMapping.entrySet()) {
            if (entry.getKey() != root && entry.getValue() * 2 == totalSum) {
                return true;
            }
        }
        return false;
    }
    
    private int calcSubTreeSum(TreeNode root, HashMap<TreeNode, Integer> subTreeSumMapping) {
        if (null == root) {
            return 0;
        }
        Integer sumObj = subTreeSumMapping.get(root);
        if (null != sumObj) {
            return sumObj;
        }
        int leftSubTreeSum  = calcSubTreeSum(root.left, subTreeSumMapping);
        int rightSubTreeSum = calcSubTreeSum(root.right, subTreeSumMapping);
        sumObj              = root.val + leftSubTreeSum + rightSubTreeSum;
        subTreeSumMapping.put(root, sumObj);
        return sumObj;
    }
    

    }


Log in to reply
 

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