very concise Java 8 solution, maintain sum of subtree rooted at each node

  • 1

    The idea is to maintain the sum of all the nodes of the subtree rooted at each node.
    Once we have this map, then go through each node and check if 2 * sum of the subtree rooted at current node == total Sum of the tree.

    This is the first time, I get to use the Java 8 stream's anyMatch function, though we do this in python all the time.

        public boolean checkEqualTree(TreeNode root) {
            if(root != null && root.left == null  && root.right == null) return false;
            Map<TreeNode, Integer> map = new HashMap<>();
            int totalSum = populateTreeSums(root, map);
            return map.values().stream().anyMatch(x -> 2 * x == totalSum);
        public int populateTreeSums(TreeNode root, Map<TreeNode, Integer> map) {
            if(root == null) return 0;
            map.put(root, populateTreeSums(root.left, map) + populateTreeSums(root.right, map) + root.val);
            return map.get(root);

Log in to reply

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