剑指offer26:树的子结构

题目:输入两棵二叉树A，B，判断B是不是A的子结构.

如上图，其中B为A的子结构.

思路: 判断是否为子树，首先需要定位到子树的根节点，然后对两颗树的左右子节点进行对比. 首先取A中根节点与B根节点对比，若值相等，则对比二者的左右子树. 当B树走到叶子节点时，表明这一条路径相等. 若根节点不等，则在左子树上寻找，若左子树没有，则去右子树寻找. 整个过程采用递归实现。

bool IsSubTree(TreeNode* pRoot1, TreeNode* pRoot2){
        if(pRoot2==nullptr)
            return true;
        if(pRoot1 ==nullptr && pRoot2!=nullptr)
            return false;
        if(pRoot1->val != pRoot2->val)
            return false;
        return IsSubTree(pRoot1->left, pRoot2->left) && IsSubTree(pRoot1->right, pRoot2->right);
    }

bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2){
        if(pRoot1==nullptr || pRoot2==nullptr)
            return false;
        bool flag=false;
        if(pRoot1->val==pRoot2->val){
             flag = IsSubTree(pRoot1, pRoot2);
        }
        if(!flag){
            if(pRoot1->left!=nullptr){
                flag= HasSubtree(pRoot1->left, pRoot2);
            }
        }
        if(!flag){
            if(pRoot1->right!=nullptr){
                flag= HasSubtree(pRoot1->right, pRoot2);
            }
        }
        return flag;
    }