剑指offer-面试题26树的子结构
目录
剑指offer - 面试题26树的子结构
此题核心就是递归。
升级的地方就是两个递归。第一层递归是遍历pRoot1作为根节点。第二层就是对每个访问到的根，判断是否和pRoot2相同（pRoot1包含pRoot2即可，pRoot1可以含有pRoot2没有的节点）。
主要的坑点就是要想明白递归的结束条件。
题目要求pRoot2是pRoot1的子树，在检查是否是子树的递归中，结束条件：pRoot2为空就可以返回true，而不需要pRoot1同时为空。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
bool checkTreeCorrespond(TreeNode* node1, TreeNode* node2) {
if (node2 == NULL) { // 一开始条件写成了node1 == NULL && node2 == NULL，导致用例{1,2,3,4,5},{1,2,3}没通过。题目中说空树不是任意一个树的子结构，这个条件只在调用checkTreeCorrespond前判断就行，保证检查的两个根节点都不是空就可以。因为只需要满足node2是node1的子树，所以node1还可以有除了node2之外的子树。这里的递归条件一定要注意，只要遍历到node2是空了，说明当前遍历到的节点都是匹配上了的。
return true;
}
if (node1 == NULL || node2 == NULL) {
return false;
}
if (node1->val == node2->val) {
return checkTreeCorrespond(node1->left, node2->left) && checkTreeCorrespond(node1->right, node2->right);
}
return false;
}
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
if (pRoot1 == NULL || pRoot2 == NULL) {
return false;
}
if (checkTreeCorrespond(pRoot1, pRoot2)) {
return true;
}
return HasSubtree(pRoot1->left, pRoot2) || HasSubtree(pRoot1->right, pRoot2);
}
};