[Java] One pass through the tree. Use Set to memorize the subtree sum


  • 0
    Z

    The idea is to calculate the sum of the tree and along the way memorize the subtree's sum in a HashSet. At the end if any subtree's sum is half the original tree's sum, we can cut that subtree off and return true.

    Note that we cannot consider the original tree as a subtree of itself, otherwise the result might be wrong if the sum of the original tree is 0.

    class Solution {
        public boolean checkEqualTree(TreeNode root) {
            Set<Integer> treeSum = new HashSet<>();
            
            int sum = root.val + sum(root.left, treeSum) + sum(root.right, treeSum);
            
            return sum % 2 == 0 && treeSum.contains(sum / 2);
        }
        
        private int sum(TreeNode root, Set<Integer> treeSum) {
            if (root == null) {
                return 0;
            }
            int sum = root.val + sum (root.left, treeSum) + sum(root.right, treeSum);
            treeSum.add(sum);
            return sum;
        }
    }
    

Log in to reply
 

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