题解 | #树的子结构#

• a. 递归遍历左侧的树，若等于右侧树根节点，则进一步判断对应左右子树是否相等。
  返回值用或||，当有一个返回true时结束遍历。
• b. 递归判断左右每一个节点是否相等，保持节点一致。
  返回值用&&，保持完全一致。注意：右侧为空时，应该返回true.

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:

    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if(!pRoot2||!pRoot1) return false;
        if(pRoot1->val == pRoot2->val) //前序遍历验证
        {
//             coutval<<" \n";
            if(isSubTree(pRoot1,pRoot2))    //从相同位置开始判断
                return true;
        }
        return HasSubtree(pRoot1->left,pRoot2)|| 
            HasSubtree(pRoot1->right,pRoot2);
    }

    bool isSubTree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        // pRoot2等于空，说明左边完全匹配右边   
        if(!pRoot2)return true;
        // 左边为空 右边为空 false
        // 值不相等也 false
        if(!pRoot1 || pRoot1->val != pRoot2->val)return false;
        return isSubTree(pRoot1->left,pRoot2->left)&&
            isSubTree(pRoot1->right,pRoot2->right);
    }
};