C++版 - 剑指offer 面试题18: 树的子结构(LintCode 245.Subtree) 题解

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool Tree1HaveTree2(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        if(pRoot2 == NULL) return true;
        if(pRoot1 == NULL) return false; // 前两个递归出口条件的顺序有影响
        if(pRoot1->val != pRoot2->val) return false;
        return (Tree1HaveTree2(pRoot1->left, pRoot2->left))&&(Tree1HaveTree2(pRoot1->right, pRoot2->right));        
    }
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        bool res = false;
        if(pRoot1 != NULL && pRoot2 != NULL)
        {
        if(pRoot1->val == pRoot2->val) res = Tree1HaveTree2(pRoot1, pRoot2);
        if(res == false) res = HasSubtree(pRoot1->left, pRoot2);
        if(res == false) res = HasSubtree(pRoot1->right, pRoot2);    
        }
        return res;
    }
};