4-liner with unordered_multiset (taking case of sum==0 case)


  • 0

    The multiset sums stores the sums of all subtrees. For the sum sum of the original tree r, we need to check if sum is even and sum/2 in the mutiset. Note that if sum == 0, we need to make sure 0 shows up at least twice in the multiset (this is the only reason I used a multiset to count the duplicity).

        bool checkEqualTree(TreeNode* r) {
            int sum = getSum(r);
            return sum%2==0 && sums.count(sum/2) > (sum==0);
        }
        
        unordered_multiset<int> sums;    
        int getSum(TreeNode* x) {
            return x? *sums.insert(x->val + getSum(x->left) + getSum(x->right)) : 0;
        }
    

Log in to reply
 

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