O(n) solution and O(1) space with no extra data structures


  • 0
    A
        bool checkEqualTree(TreeNode* root) {
            if(!root) return true;
            sum(root);
            bool retVal= helper(root, 0);
            deSum(root);
            return retVal;
        }
        void deSum(TreeNode*r){
            if(!r) return;
            if(r->left) r->val-=r->left->val;
            if(r->right) r->val-=r->right->val;
        }
        int sum(TreeNode*r){
            if(!r) return 0;
            r->val+=sum(r->left);
            r->val+=sum(r->right);
            return r->val;
        }
        bool helper(TreeNode* r, int curWeight){
            if(!r) return false;
            int realRootValWithLeft = r->val+curWeight;
            int realRootValWithRight = r->val+curWeight;
            
            if(r->left) realRootValWithRight-=r->left->val;        
            if(r->right) realRootValWithLeft-=r->right->val;
            
            if(r->right && realRootValWithLeft==r->right->val) return true;
            else if(r->left && realRootValWithRight==r->left->val) return true;
            
            return helper(r->left, realRootValWithRight) || helper(r->right, realRootValWithLeft);
        }
    

Log in to reply
 

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