题解 | #树的子结构#

分为三种情况：

1. pRoot1->val == pRoot2->val：需要检查pRoot2的左子树、右子树是否分别是pRoot1的左子树、右子树的子树，如果都是则返回true，否则还有可能是情况2、3。
2. pRoot2是pRoot1左子树的子树，递归调用即可。
3. pRoot2是pRoot1右子树的子树，递归调用即可。

有一点需要注意的是，约定nullptr不是任何树的子树，这就导致了在pRoot2为单节点时需要特殊处理，否则会返回错误的值。我们在pRoot1->val == pRoot2->val当中进行处理，只有当pRoot2的左右子树不为空时才进行递归调用。

class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
		if (!pRoot1 || !pRoot2) return false;
		if (pRoot1->val == pRoot2->val) {
			bool res = true;
			if (pRoot2->left) res = res && HasSubtree(pRoot1->left, pRoot2->left);
			if (pRoot2->right) res = res && HasSubtree(pRoot1->right, pRoot2->right);
			if (res) return true;
		}
		return HasSubtree(pRoot1->left, pRoot2) || HasSubtree(pRoot1->right, pRoot2);
    }
};