描述

示例

思路一：递归

知识点：二叉树递归 递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。

思路

既然是要找到A树中是否有B树这样子树，如果是有子树肯定是要遍历这个子树和B树，将两个的节点一一比较，但是这样的子树不一定就是A树根节点开始的，所以我们还要先找到子树可能出现的位置。

既然是可能的位置，那我们可以对A树的每个节点前序递归遍历，寻找是否有这样的子树，而寻找是否有子树的时候，我们就将A树与B树同步前序遍历，依次比较节点值。

步骤

• 因为空树不是任何树的子树，所以要先判断B树是否为空树。
• 当A树为空节点，但是B树还有节点的时候，不为子树，但是A树不为空节点，B树为空节点时可以是子树。
• 每次递归比较A树从当前节点开始，是否与B树完全一致，同步前序遍历。
• A树自己再前序遍历进入子节点，当作子树起点再与B树同步遍历。
• 以上情况任意只要有一种即可。

代码

    /*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/

class Solution {

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

思路二：两层层次遍历

根据方法一，所以这道题的思路，无非就是在A树中遍历每个节点尝试找到那个子树，然后每次以该节点出发能不能将子树与B树完全匹配。能用前序遍历解决，我们也可以用层次遍历来解决。

首先对于A树层次遍历每一个节点，遇到一个与B树根节点相同的节点，我们就开始同步层次遍历比较以这个节点为根的树中是否出现了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);
    //以树2为基础，树1跟随就可以了
    while(!q2.empty()){
        TreeNode* node1 = q1.front();
        TreeNode* node2 = q2.front();
        q1.pop();
        q2.pop();
        //树1为空或者二者不相等
        if(node1 == NULL || node1->val != node2->val)
            return false;
        //树2还有左子树
        if(node2->left){
            //子树入队
            q1.push(node1->left);
            q2.push(node2->left);
        }
        //树2还有右子树
        if(node2->right){
            //子树入队
            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);
    //层次遍历树1
    while(!q.empty()){
        TreeNode* node = q.front();
        q.pop();
        //遇到与树2根相同的节点，以这个节点为根判断后续子树是否相同
        if(node->val == pRoot2->val){
            if(helper(node, pRoot2))
                return true;
        }
        //左子树入队
        if(node->left)
            q.push(node->left);
        //右子树入队
        if(node->right)
            q.push(node->right);
    }
    return false;
}
};