题解 | #树的子结构#

思路：

题目的主要信息：

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

方法一：两层先序遍历
具体做法：
对A树的每个结点递归遍历（先序），寻找是否有这样的子树，而寻找是否有子树的时候也是用递归，但这次是A树与B树同步先序遍历，遍历完一个B树或者有不相等的结点为止。
图片说明

class Solution {
public:
    bool function(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 function(root1->left, root2->left) && function(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 = function(pRoot1, pRoot2);  //递归比较
        bool flag2 = HasSubtree(pRoot1->left, pRoot2);  //递归树1的每个结点
        bool flag3 = HasSubtree(pRoot1->right, pRoot2);
        return flag1 || flag2 || flag3;
    }
};

复杂度分析：

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

方法二：两层中序遍历
具体做法：
与先序遍历类似，只不过递归时遵循先左再中后右的思想。

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

复杂度分析：

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