解决这个题分两步
1.遍历树A中的所有非空节点
2.判断A中以R为根节点的子树是不是和树B是一样的结构,并且从根节点匹配
对于第一部分: 直接递归遍历树,遇到空节点进行第二步操作
对于第二部分: 从根节点遍历两棵树
- 如果树B是空的,则与当前分支匹配,返回true
- 如果树A是空的,但是B不为空,返回false
- 如果两个节点都不是空的,但数值不同,则不匹配,返回false
- 否则说明匹配,递归遍历左右子树
/**
* 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) {
if(!pRoot1||!pRoot2) return false;//如果有一个树为空
if(ispart(pRoot1,pRoot2)) return true;//如果匹配
return hasSubtree(pRoot1->left,pRoot2)||hasSubtree(pRoot1->right,pRoot2);//既不为空也不匹配,就对他的左右分支进行搜索
}
bool ispart(TreeNode *pRoot1,TreeNode *pRoot2)//判断是否匹配
{
if(!pRoot2) return true;//第一个条件
if(!pRoot1||pRoot1->val!=pRoot2->val) return false;//第二三个条件
return ispart(pRoot1->left,pRoot2->left)&&ispart(pRoot1->right,pRoot2->right);
}
};