题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。

我们规定空树不是任何树的子结构。

样例

     8
    / \
   8   7
  / \
 9   2
    / \
   4   7

   8
  / \
 9   2

算法

(递归、二叉树)

1. 老样子，还是先推荐大家去看y总的题解，有视频有图文，很棒。我这里说一些代码的实现细节hh。
2. 首先判断两个二叉树为空的情况，如果为空，直接return false;
3. 如果不为空，就可以调用isPart(A, B)函数来判断B是否为A的子树。如果不是，则递归，判断B是否是A的左子树的子树，或者，B是否是A的右子树的子树。注意是||
4. 对于函数isPart(A, B)的细节。首先判断B子树的节点是否为空，如果为空，说明前面的都匹配，直接return true
5. 接下来，如果B树的节点不为空，但是A树的节点为空，那么一定不匹配，直接return false。
6. 如果A和B树的节点都不为空，但是值不一样，那也是不匹配，直接return false
7. 最后如果 B树的节点不为空， A树的节点也不为空， A树和B树的当前节点是匹配的。那么我们就递归到A和B的左子树，同时，A和B的右子树，看看是否匹配，注意这里是&&。

代码模拟

1. 刚理解地不够透彻，又对着样例和代码手动模拟了一遍。
2. 在isPart()函数中，如果B对应的节点是NULL，则说明它的父节点已经和A的对应位置已经匹配了，那么就直接return true。
3. 一开始A树看的都是 根结点，根结点不匹配了再看A的左子树或者A的右子树。
4. 比较的时候isPart，也是比较A的根结点的左子树和整个B树的对应。如果该点匹配， 就同时看两个树A和B中左子树和右子树是否都匹配，如果是则true，不是则false;
5. isPart()中的顺序不能改。

   • 先判断B的节点是否为空，是的话说明该节点的父节点已经匹配，return true
   • 这时，再判断A的节点是否为空，走到这句说明B的节点不为空，如果A空B不空，一定不匹配，return false
   • 第3句，说明A和B都不为空，就看对应的val是否相等，不等就return false；相等的话就向下递归，看这个节点在2棵树中对应的左右子树是否匹配。

时间复杂度

$O(nm)$
最坏情况下，对于树A中的每个节点都要递归判断一遍，每次判断在最坏情况下需要遍历完树B中的所有节点。
因此时度是$O(nm)$，其中，$n$是树A中的节点数，$m$是树B中的节点数。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if(!pRoot1 || !pRoot2) return false;
        if(isPart(pRoot1, pRoot2)) return true;

        return hasSubtree(pRoot1->left, pRoot2) || hasSubtree(pRoot1->right, pRoot2);  // **3
    }

    bool isPart(TreeNode *A, TreeNode *B)
    {
        if(!B) return true;
        if(!A) return false;
        if(A->val != B->val) return false;                         // **2
        return isPart(A->left, B->left) && isPart(A->right, B->right);   // **1
    }
};