输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

/*
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
思路：递归方法。
分解为两步：
1.遍历A树，找到与B中根节点值一样的节点，这就相当于树的遍历，用递归操作。
2.若第一步中找到合适的根节点，再检查对应左右子树是否满足条件。
扫描A树，若找到A的某一个节点pA与B的根节点值相同。则继续扫描pA左右子树与B左右子树是否一致，若整个递归过程都返回true，则B是A的子结构；
若在递归过程中有一处返回false，则继续遍历A节点直至返回true或者遍历完。
*/
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
/*
1.遍历A树，找到与B根节点一样的节点，若找到，转2；若没找到，则在A的左右子树上找，一直到遍历完。
*/
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
    if (pRoot1 == nullptr || pRoot2 == nullptr)
        return false;
    bool result = false;
    if (pRoot1 != nullptr && pRoot2 != nullptr)
    {
        //若根节点相同，则转2，判断其左右子树是否也相同
        if (pRoot1->val == pRoot2->val)
            result = DoesTree1HaveTree2(pRoot1, pRoot2);
        //若上述结果为false,则继续遍历A的左子树，找到下一个与B根节点相同的节点
        if (!result)
            result= HasSubtree(pRoot1->left, pRoot2);
        //若左子树查找结果仍为false,则继续遍历A的右子树，找到下一个与B根节点相同的节点
        if (!result)
            result= HasSubtree(pRoot1->right, pRoot2);
    }
    return result;
}
/*
2.若在1中找到对应的相同的节点，则在此节点上继续遍历是否左右子树也一样
*/
bool DoesTree1HaveTree2(TreeNode* pRoot1, TreeNode* pRoot2)
{
    //若B树遍历完了到达结尾了，说明都能对应上，返回true;
    if (pRoot2 == nullptr)
        return true;
    //若比较过程中出现不对应的地方，则返回false;
    if (pRoot1->val != pRoot2->val)
        return false;
    //若A树遍历完了，B树还没完，则说明对应不上，返回false
    if (pRoot1 == nullptr)
        return false;

    //否则，递归继续比较左右节点是否相同
    return DoesTree1HaveTree2(pRoot1->left, pRoot2->left) && DoesTree1HaveTree2(pRoot1->right, pRoot2->right);
}