LeetCode 572. Subtree of Another Tree

Recursive

对于s的每一个节点，我们都要调用isSame来判断两棵树是否相同。

时间复杂度 O(mn)

class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if (s==NULL && t==NULL) return true;
        if (s==NULL) return false;
        return isSame(s,t) || isSubtree(s->left,t) || isSubtree(s->right,t);
    }
    
    bool isSame(TreeNode *a, TreeNode *b){
        if (a==NULL && b==NULL) return true;
        if (a==NULL || b==NULL) return false;
        return a->val==b->val && isSame(a->left,b->left) && isSame(a->right,b->right);
    }
};

 

PreOrder + Serialize

本质就是用preOrder来serialize两个树。如果t是子树，那么序列化之后，t一定是s的字串。

假设concatenate长度为n的字符串时间为O(n)，serialize对于每个节点都要concatenate一下，时间复杂度O(n^2)。

需要注意的是serialize函数，to_string(root->val) 前又加了一个' '，这是为了防止诸如 "2 # #" 在 "12 # #" 中的情况产生。

class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        string s1=serialize(s);
        string s2=serialize(t);
        return s1.find(s2)!=-1;
    }
    
    string serialize(TreeNode* root) {
        if (root==NULL) return "#";
        return ' '+to_string(root->val)+' '+serialize(root->left)+' '+serialize(root->right);
    }
};