A one-pass C++ solution with hash table


  • 0

    Compute the sum of every single subtree and store it in the hash table while computing the sum of the entire tree.

    bool checkEqualTree(TreeNode* r) {
        unordered_set<int> s;
        int p = sum(r, s, true);
        return !(p % 2) && s.count(p / 2) > 0;
    }
    
    int sum(TreeNode *r, unordered_set<int> &s, bool isroot) {
        if (!r) return 0;
        auto v = r->val + sum(r->left, s, false) + sum(r->right, s, false);
        return isroot ? v : *s.insert(v).first;
    }
    

Log in to reply
 

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