题解 | #树的子结构#

/*
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 (pRoot1 == nullptr || pRoot2 == nullptr)	return false;
		bool res = false;
		if (pRoot1->val == pRoot2->val) {
			res = isPart(pRoot1, pRoot2);
		}
		// 如果找不到，就找左子树
		if (!res) {
			res = HasSubtree(pRoot1->left, pRoot2);
		}
		// 左子树找不到，就找右子树
		if (!res) {
			res = HasSubtree(pRoot1->right, pRoot2);
		}
		return res;
    }
	
	bool isPart(TreeNode* t1, TreeNode* t2) {
		// 节点值相同才会进入isPart函数，终止条件就是到 t1 或 t2 的叶子节点
		if (t2 == nullptr) return true;
		// 如果 t2 还没有遍历完，t1 却遍历完了。返回false
		if (t1 == nullptr) return false;
		if (t1->val != t2->val) return false;
		return isPart(t1->left, t2->left) && isPart(t1->right, t2->right);
	}


};