题解 | #树的子结构#

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
	bool dfs(TreeNode* parent, TreeNode* son) {
		if (son == nullptr) return true;
		if (parent == nullptr) return false;
		if (parent->val != son->val) return false;

		bool left = dfs(parent->left, son->left);
		bool right = dfs(parent->right, son->right);
		return left && right;
	}
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
		if (pRoot1 == nullptr || pRoot2 == nullptr) return false;
		queue<TreeNode*> q;
		q.push(pRoot1);
		while (!q.empty()) {
			int cnt = q.size();
			while (cnt > 0) {
				TreeNode *temp = q.front();
				q.pop();
				if (dfs(temp, pRoot2)) return true;
				if (temp->left) q.push(temp->left);
				if (temp->right) q.push(temp->right);
				cnt--;
			}
		}
		return false;
    }
};