C++ O(N) short solution without using multiset or multimap


  • 0
    A

    Pseudo Code:

    • Calculate the sum of given tree, store it in sum
    • Check if there is any subtree whose sum = sum / 2 and sum should be even, return true otherwise false.
    • To deal with test cases where sum = 0, we need to check whether there exist more than one sub-tree whose sum = sum / 2.
    class Solution {
    public:
        int ans;
        int sumOfTree(TreeNode* root) {
            if(root == NULL) return 0;
            return sumOfTree(root -> left) + sumOfTree(root -> right) + root -> val;
        }
        int hasSum(TreeNode* root, int need) {
            if(!root) return 0;
            int sum = hasSum(root -> left, need) + hasSum(root -> right, need) + root -> val;
            if(sum == need) ans++;
            return sum;
        }
        bool checkEqualTree(TreeNode* root) {
            int sum = sumOfTree(root);
            ans = 0;
            if(sum % 2) return ans;
            hasSum(root, sum / 2);
            return sum == 0 ? ans > 1 : ans > 0;
        }
    };
    

Log in to reply
 

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