题目描述:
输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

思路:
1.首先查找A中是否有与B的根节点一样的值
2.若没有,则判断结束,B不是A的子树
3.若有,则判断根节点的左右节点的值是否相同,若不同,则不是,
若相同,则判断左节点的左右节点是否相同,若相同,则判断右节点的左右节点是否相同
4.递归至达到A或B的叶子节点结束

实现:
这位大佬的逻辑短路用得很溜,所以借鉴一下下~

链接:https://www.nowcoder.com/questionTerminal/6e196c44c7004d15b1610b9afca8bd88
来源:牛客网

class Solution {
    bool isSubtree(TreeNode* pRootA, TreeNode* pRootB) {
        if (pRootB == NULL) 
        	return true;
        if (pRootA == NULL) 
        	return false;
        if (pRootB->val == pRootA->val) {              //先找A中有没有与B根节点一样的值,有再比较左右子树是否相同
            return isSubtree(pRootA->left, pRootB->left)&& isSubtree(pRootA->right, pRootB->right);
        } else 
        	return false;            //没有则说明B不是A的子树
    }
public:
    bool HasSubtree(TreeNode* pRootA, TreeNode* pRootB)
    {
        if (pRootA == NULL || pRootB == NULL)     //递归的终止条件是达到了A或者B的叶节点
        	return false;
        return isSubtree(pRootA, pRootB) ||HasSubtree(pRootA->left, pRootB) || HasSubtree(pRootA->right, pRootB);   //借助逻辑短路
    }
};