题解 | #树的子结构#

树的子结构：最直观的想法是，使用双指针，一个指针指向A，一个指针指向B，首先遍历树A，然后针对树A的当前结点，判断B是否是以当前结点为根的子树的子结构。

//判断B是否是和以A为根的子树匹配
bool isSame(TreeNode *pRoot1,TreeNode *pRoot2)
{
    //递归出口是如果pRoot2为空则为真
    if(!pRoot2)
      return true;
    //反之如果pRoot2不为空但是pRoot1为空则为假
    else if(!pRoot1)
      return false;
    //B和以A为根的子树匹配所需要满足的条件即为：B和A当前节点相等且B的左与A的左匹配且B的右和A的右匹配
    return pRoot1->val==pRoot2->val&&isSame(pRoot1->left,pRoot2->left)&&isSame(pRoot1->right,pRoot2->right);
}
//判断树B是否是树A的子结构 其中是B是整个树A的子结构 并不一定是以A为根节点的 即A的根节点与B的根节点相等的匹配
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) 
{
    //递归出口即为A或者B为空树则为false
    if(!pRoot1||!pRoot2)
       return false;
    //B是A的子结构所需要满足的条件即为：B是以A为根节点的子树或者B是A的左孩子树的子结构或者B是A的右孩子的子结构
    return isSame(pRoot1,pRoot2)||HasSubtree(pRoot1->left,pRoot2)||HasSubtree(pRoot1->right,pRoot2);
}