C++, DFS two pass without using hashtable, O(n)


  • 0
    Z

    First, get the sum of the tree, let's say, S. Then, check whether there is a subtree with sum == S/2 and S is even.

    class Solution {
    public:
        bool checkEqualTree(TreeNode* root) {
            if (!root) return false;
            int sum = tree_sum(root);
            if (sum%2) return false;
            bool ans = false;
            helper(root->left, ans, sum/2);
            helper(root->right, ans, sum/2);
            return ans;
        }
    private:
        int tree_sum(TreeNode* p) {
            if (p == NULL) return 0;
            return tree_sum(p->left)+tree_sum(p->right)+p->val;
        }
        int helper(TreeNode* p, bool& ans, int sum) {
            if (ans || p == NULL) return 0;
            int left = helper(p->left, ans, sum);
            if (ans) return 0;
            int right = helper(p->right, ans, sum);
            if (ans) return 0;
            int tot = left+right+p->val;
            ans = tot == sum;
            return tot;
        }
    };
    

Log in to reply
 

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