问题抽象

A, B为二叉树，判断B是否是A的子结构（与A的某部分完全相同，A中有完整的B）
约定空树不是任何树的子结构

算法：DFS

这道题的难点在于，要确定A整体中是否有B，就必须从A的局部出发看是否有B，因此是两层遍历：
1. 遍历A的非空节点
2. 再从这个节点出发与B递归比较，看是否有完整的B

其中第二步又分为三小步：
1. 若递归遍历到B为空，则B有的A都有，返回true
2. 若递归遍历到A为空，则B有的A没有，返回false
3. 若都不为空，则比较当前节点值，并继续递归遍历A, B左右两边即可。

时间复杂度

$O(NM)$

代码

/**
 * 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 isSubStructure(TreeNode* A, TreeNode* B) { // 把整个A拿来看，有没有B的子结构
        if(!A || !B) return false;
        if(dfs(A, B)) return true;
        return isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }
    bool dfs(TreeNode *a, TreeNode *b){ // 从A的某个根节点a开始看，有没有B的子结构
        if(!b) return true;
        if(!a) return false;
        return a->val == b->val && dfs(a->left, b->left) && dfs(a->right, b->right);
    }
};