题解 | 树的子结构

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
	bool DoesTree1HaveTree2(TreeNode* pRoot1, TreeNode* pRoot2) {
		// 如果B树为空，说明已遍历完
		if (pRoot2 == nullptr) return true;
		// 如果A树为空，说明B树还没遍历完
		if (pRoot1 == nullptr) return false;
		// 比较根节点值
		if (pRoot1->val != pRoot2->val) return false;
		// 走得通，则再递归判断子树
		return DoesTree1HaveTree2(pRoot1->left, pRoot2->left) && DoesTree1HaveTree2(pRoot1->right, pRoot2->right);
	}
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
		bool result = false;
		if (pRoot1 != nullptr && pRoot2 != nullptr) {
			if (pRoot1->val == pRoot2->val)
				result = DoesTree1HaveTree2(pRoot1, pRoot2);
			if (!result)
				result = HasSubtree(pRoot1->left, pRoot2);
			if (!result)
				result = HasSubtree(pRoot1->right, pRoot2);
		}
		return result;
    }
};