题解 | #JZ26 树的子结构#

//子函数递归

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    bool traceSubTree(TreeNode* pRoot1, TreeNode* pRoot2) {
        //递归退出条件：B为空时返回真；否则A非空时返回假
        if (!pRoot2) return true;
        else if (!pRoot1) return false;
        
        //若当前值相等且左右子树相等，则返回真
        if (pRoot1->val == pRoot2->val && traceSubTree(pRoot1->left, pRoot2->left) && traceSubTree(pRoot1->right, pRoot2->right)) return true;
        //否则，若A的左子树等于B则返回真
        if (pRoot1->left && traceSubTree(pRoot1->left, pRoot2)) return true;
        //否则，若A的右子树等于B则返回真
        if (pRoot1->right && traceSubTree(pRoot1->right, pRoot2)) return true;
        
        //否则，返回假
        return false;
    }
    
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if (!pRoot2 || !pRoot1) return false;
        
        return traceSubTree(pRoot1, pRoot2);
    }
};