文章目录
分析
从主树A的根开始，依次判断B是否是A的子结构。
可以分三种情况：
- 两个根root1和root2都空，返回false
- 两个根开始的树匹配，返回true
- 否则，递归遍历root1->left 和root2是否匹配， root1->right 和root2是否匹配。
具体匹配为函数isPart(r1,r2)
- 如果r2为空，表示匹配成功
- 如果r1为空，表示匹配失败。
- 如果r1的值不等于r2的值，表示匹配失败。
- 否则递归遍历r1->left和r2->left ，r1->right 和r2->right是否匹配。
ac代码
/**
* 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) {
// 其中只要有一个是空的就返回false
if (!pRoot1 || !pRoot2) return false;
// root1和root2匹配。
if (isPart(pRoot1, pRoot2)) return true;
// 分别递归左右子树left和root2匹配或者right和root2匹配
return hasSubtree(pRoot1->left, pRoot2) || hasSubtree(pRoot1->right, pRoot2);
}
bool isPart(TreeNode *p1, TreeNode *p2) {
// 第二个根是空的，代表该分支是匹配的。
if (!p2) return true;
// 第一个是空的，代表不匹配
if (!p1) return false;
// 如果都不空，两个值不同，代表不匹配
if (p1->val != p2->val) return false;
// 左边对左边，右边对右边分别判断是否匹配
return isPart(p1->left, p2->left) && isPart(p1->right, p2->right);
}
};
时间复杂度: O ( m n ) O(mn) O(mn),m为第一棵树的结点数，n为第二棵树的结点数
题目来源
https://www.acwing.com/problem/content/35/