AcWing 37. 树的子结构
原题链接
简单
作者:
KillLemon
,
2020-12-10 12:07:54
,
所有人可见
,
阅读 474
/**
* 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* p1, TreeNode* p2) {
//判断子树需要判断三种情况,1.是否是当前树的相同,如果相同return true
//2.是否是当前左右子树的子树
//递归终止条件如果比较难判断可以在写完递归主体后回来看
if(!p1 || !p2) return false;
if(isSame(p1,p2)) return true;
return hasSubtree(p1->left,p2) || hasSubtree(p1->right,p2);
}
bool isSame(TreeNode* p1, TreeNode* p2){
if(!p2) return true;
if(!p1 || p2->val != p1->val) return false; //!p1要在p2->val != p1->val前面判断
return isSame(p1->left,p2->left) && isSame(p1->right,p2->right);
}
};