题解
// 树的子结构
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
// 初始化:树A和树B的根节点pRoot1, pRoot2
// 遍历树A,cur指向当前节点,将cur作为根节点的子树C与pRoot2作为根节点的子树进行比较,若后者是前者的子结构,则返回true否则为false
if (!pRoot1 || !pRoot2) return false;
return is_equ(pRoot1, pRoot2) || is_equ(pRoot1->left, pRoot2) || is_equ(pRoot1->right, pRoot2);
}
// // 树的先序遍历
// void pre(TreeNode* root)
// {
// // 对root做点什么
// pre(root->left);
// pre(root->right);
// }
// 判断是否有相同的结构
bool is_equ(TreeNode* pRoot1, TreeNode* pRoot2){
// 初始化,两颗子树的根节点,pRoot1, pRoot2
// 若pRoot1和pRoot2的内容不等,直接返回false, 若相等则递归判断其左子树和右子树是否相等
// 若pRoot1为空,pRoot2不为空,则判为false
// 若pRoot1不为空,pRoot2为空,则判为true
if (!pRoot2) return true; // pRoot2为空
if (!pRoot1) return false;
return (pRoot1->val==pRoot2->val) && is_equ(pRoot1->left, pRoot2->left) && is_equ(pRoot1->right, pRoot2->right);
}
难点
- 第7行,顶层设计,即判断树B是树A的子结构的条件:(1)树B是以树A为根节点的树的子结构;(2)树B是以树A的左子树中的子结构;(3)树B是树A中右子树的子结构;
- 第19,26行,设计以pRoot2为根节点的树是否是以pRoot1为根节点的递归函数