题目的主要信息：

• 给定两棵二叉树的层次遍历序列
• 判断二叉树B是否为A树的子树
• 我们约定空树不是任意一个树的子结构

方法一：两层先序遍历

具体做法：

对A树的每个结点递归先序遍历，寻找是否有这样的子树，而寻找是否有子树的时候也是用递归，但这次是A树与B树同步先序遍历，遍历完一个B树或者有不相等的结点为止。

class Solution {
public:
    bool recursion(TreeNode* root1, TreeNode* root2){
        if(root1 == NULL && root2 != NULL)  //当一个结点存在另一个不存在时
            return false;
        if(root1 == NULL || root2 == NULL)  //两个都为空则返回
            return true;
        if(root1->val != root2->val)
            return false;
        return recursion(root1->left, root2->left) && recursion(root1->right, root2->right);
    }
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if(pRoot2 == NULL) //空树
            return false;
        if(pRoot1 == NULL && pRoot2 != NULL)
            return false;
        if(pRoot1 == NULL || pRoot2 == NULL)
            return true;
        bool flag1 = recursion(pRoot1, pRoot2);  //递归比较
        bool flag2 = HasSubtree(pRoot1->left, pRoot2);  //递归树1的每个结点
        bool flag3 = HasSubtree(pRoot1->right, pRoot2);
        return flag1 || flag2 || flag3;
    }
};

复杂度分析：

• 时间复杂度：$O(nm)O(nm)$，$nn$和$mm$分别表示两棵树的结点数，我们要对每个A树节点进行访问，最坏情况下每次都要比较B树节点的次数
• 空间复杂度：$O(nm)O(nm)$，两个递归栈深度相乘(当树退化成链表时，递归栈最大）

方法二：两层层次遍历

具体做法：

我们也可以用层次遍历来解决。首先对于A树层次遍历每一个结点，遇到一个与B树根节点相同的结点，我们就调用helper函数比较以这个结点为根的树中是否出现了B树的全部结点。因为我们只考虑B树的所有结点是否在A树中全部出现，那我们就以B树为基，再进行一次层次遍历，A树从那个结点开始跟随B树一致进行层次遍历就行了，比较对应的每个点是否相同，或者B树是否有超出A树没有的结点。

层次遍历我们借助队列，根结点入队，然后取值，然后左右结点如果有就入队，每次队列弹出一个结点，知道队列为空，这样刚好是一层一层读取数据。

class Solution {
public:
    bool helper(TreeNode* root1, TreeNode* root2){ //层次遍历判断两个树是否相同
        queue<TreeNode*> q1, q2;
        q1.push(root1);
        q2.push(root2);
        while(!q2.empty()){ //以树2为基础，树1跟随就可以了
            TreeNode* node1 = q1.front(); 
            TreeNode* node2 = q2.front();
            q1.pop();
            q2.pop();
            if(node1 == NULL || node1->val != node2->val) //树1为空或者二者不相等
                return false;
            if(node2->left){ //树2还有左子树
                q1.push(node1->left); //子树入队
                q2.push(node2->left);
            }
            if(node2->right){ //树2还有右子树
                q1.push(node1->right); //子树入队
                q2.push(node2->right);
            }
        }
        return true;
    }
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if(pRoot1 == NULL || pRoot2 == NULL) //空树
            return false;
        queue<TreeNode*> q;
        q.push(pRoot1);
        while(!q.empty()){ //层次遍历树1
            TreeNode* node = q.front();
            q.pop();
            if(node->val == pRoot2->val){ //遇到与树2根相同的结点，以这个结点为根判断后续子树是否相同
                if(helper(node, pRoot2))
                    return true;
            }
            if(node->left) //左子树入队
                q.push(node->left);
            if(node->right) //右子树入队
                q.push(node->right);
        }
        return false;
    }
};

复杂度分析：

• 时间复杂度：$O(nm)O(nm)$，$nn$和$mm$分别表示A树和B树的结点数，我们要对每个A树节点进行访问，最坏情况下每次都要比较B树节点的次数
• 空间复杂度：$O(n)O(n)$，三个队列的长度最坏都不会超过A树的节点数