This question has one trap that is not included in the test cases


  • 0
    J

    I could be wrong but s is binary tree, not BST. There is also no assumption that every node has unique values. So if s has two children with the same value with t, and the right subtree is identical to t but not the left one, all recursive solutions that returns checkLeft && checkRight will give the wrong answer.

    Like this:

    s:
    0
    1 1
    2 3 2

    t:
    1
    2

    My solution (32ms) looks long but it handles this case. Please feel free to point out my mistakes.

    class Solution {
        vector<TreeNode*> res;
    public:
        //first trap: there can be multiple root(t) in s, need to find them all
        void findTinS(TreeNode* s, TreeNode*t) {
            if(!s || !t) return;
            if (s->val == t->val) res.push_back(s);
            findTinS(s->left, t);
            findTinS(s->right, t);
            return;
        }
        
        bool sameTree(TreeNode* A, TreeNode* B) {
            if (!A && !B) return true;
            if (!A || !B || A->val != B->val) return false;
            return sameTree(A->left, B->left) && sameTree(A->right, B->right); 
        }
        
        bool isSubtree(TreeNode* s, TreeNode* t) {
            if (!s && !t) return true;
            findTinS(s, t);
            if (res.empty()) return false;
            
            //second trap: for every root(t) in s, return true as long as one has the same structure with t
            vector<bool> allRes;
            for (auto node : res) allRes.push_back(sameTree(node->left, t->left) && sameTree(node->right, t->right)); 
            
            for(auto i : allRes) {if (i) return i;}
            return false;
        }
    };
    

Log in to reply
 

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