描述

这是一篇针对初学者的题解。
知识点：树，递归
难度：二星

题解

题目抽象：给2棵树A，树B，判断B是否是A的子结构。
子结构定义：树A和树B的根结点相等，并且树A的左子树和树B的左子树相等，树A的右子树和树B的右子树相等

方法：递归求解

第一步：
根据题意可知，需要一个函数判断树A和树B是否有相同的结构。显然是个递归程序。可考察递归程序3部曲。

1. 递归函数的功能：判断2个数是否有相同的结构，如果相同，返回true，否则返回false
2. 递归终止条件：

• 如果树B为空，返回true，此时，不管树A是否为空，都为true
• 否则，如果树B不为空，但是树A为空，返回false，此时B还没空但A空了，显然false

3. 下一步递归参数：

• 如果A的根节点和B的根节点不相等，直接返回false
• 否则，相等，就继续判断A的左子树和B的左子树，A的右子树和B的右子树

  代码

bool dfs(TreeNode *r1, TreeNode *r2) {
    if (!r2) return true;
    if (!r1) return false;
    return r1->val==r2->val && dfs(r1->left, r2->left) && dfs(r1->right, r2->right);
}

第二步：
有了上面那个函数，接下来就应该让树A的每个节点作为根节点来和B树进行比较。
遍历树A的每个节点，可用遍历算法。这里采用先序遍历。
先序遍历的模板：

void preOrder(TreeNode *r) {
    if (!r) return;
    // process r
    preOrder(r->left);
    preOrder(r->right);
}

这里用个例子来展示上述的分析：

因此，结合两个函数。可得到整个函数的代码、

bool dfs(TreeNode *r1, TreeNode *r2) {
    if (!r2) return true;
    if (!r1) return false;
    return r1->val==r2->val && dfs(r1->left, r2->left) && dfs(r1->right, r2->right);
}

bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
    if (!pRoot1 || !pRoot2) return false;
    return dfs(pRoot1, pRoot2) || HasSubtree(pRoot1->left, pRoot2) ||
    HasSubtree(pRoot1->right, pRoot2);

}

时间复杂度：O（m），m为A树的节点数，n为B树的节点数。首先A树中的每个节点必须遍历一次，然后
A树中最多有(m/n)个与B树的根节点相等，然后(m/n)n=m,所以时间复杂度为O（2m）

技巧

一般返回bool类型的递归程序，&& 与 || 的灵活使用，可以使代码非常简洁。