给定两棵二叉树 tree1 和 tree2，判断 tree2 是否以 tree1 的某个节点为根的子树具有 相同的结构和节点值 。
注意，空树 不会是以 tree1 的某个节点为根的子树具有 相同的结构和节点值 。

示例 1：

**输入：**tree1 = [1,7,5], tree2 = [6,1]
**输出：**false
**解释：**tree2 与 tree1 的一个子树没有相同的结构和节点值。

示例 2：

**输入：**tree1 = [3,6,7,1,8], tree2 = [6,1]
**输出：**true
**解释：**tree2 与 tree1 的一个子树拥有相同的结构和节点值。即 6 - > 1。

提示：

0 <= 节点个数 <= 10000

判断一个树是不是另一个树的子结构，假设是的，且根节点为A和B

则可以通过递归check判断

A->val==B->val&&check(A->left, B->left) && check(A->right, B->right);为true

如果根节点对应的不是A的根节点，则我们可以分别判断A的左右子树可不可以作为根节点

即isSubStructure(A->left, B) || isSubStructure(A->right, B);

综上就是遍历A树中的每个根节点，看其能不能作为子结构的根节点

然后注意nullptr的情况：

对于isSubStructure()，题目要求A、B中任何一方为空直接返回false

对于check()，如果B为nullptr则说明B遍历完了返回true，

如果A为nullptr，B不为，则说明B还没遍历完，A已经结束了，返回false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isSubStructure(TreeNode *A, TreeNode *B) {
        if (A == nullptr || B == nullptr)
            return false;
        return check(A, B) ||
               isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }
    bool check(TreeNode *A, TreeNode *B) {
        if (B == nullptr)
            return true;
        else if (A == nullptr)
            return false;
        return A->val == B->val &&
               check(A->left, B->left) && check(A->right, B->right);
    }
};