C++ 12 lines in place solution beats 99% (Missing TC found)


  • 0
        bool isSubtree(TreeNode* s, TreeNode* t) {
            if(!s||!t) return !s&&!t;
            bool find=false;
            if(s->val==t->val){
                bool l=false;
                bool r=false;
                if(!s->left||!t->left) l=!s->left&&!t->left;
                else if(s->left->val==t->left->val) l=isSubtree(s->left,t->left);
                if(!s->right||!t->right) r=!s->right&&!t->right;
                else if(s->right->val==t->right->val) r=isSubtree(s->right,t->right);
                find=l&&r;
            }
            return find||isSubtree(s->left,t)||isSubtree(s->right,t);
        }
    

    #EDIT:
    I found the above solution misses the case of
    [4,1,null,1,null,6,7]
    [4,1,null,6,7]
    should be false but returns true and still passed.
    Here is the correct version.

        bool isSubtree(TreeNode* s, TreeNode* t) {
            if(!s||!t) return !s&&!t;
            return found(s,t)||isSubtree(s->left,t)||isSubtree(s->right,t);
        }
        
        bool found(TreeNode* s,TreeNode* t){
            if(!s||!t) return !s&&!t;
            bool find=false;
            if(s->val==t->val){
                bool l=false;
                bool r=false;
                if(!s->left||!t->left) l=!s->left&&!t->left;
                else if(s->left->val==t->left->val) l=found(s->left,t->left);
                if(!s->right||!t->right) r=!s->right&&!t->right;
                else if(s->right->val==t->right->val) r=found(s->right,t->right);
                find=l&&r;
            }
            return find;
        }
    

Log in to reply
 

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