递归法

• 问题拆分成：已知头节点比较两颗树是否相同（递归函数一）+ 遍历树的节点作为比较起点（递归函数二）
• 注意空指针判断

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
	bool isSame(TreeNode* pRoot1,TreeNode* pRoot2)
	{
		if(!pRoot1&&pRoot2)
		{
			return false;
		}
		//pRoot1!=nullptr
		if(!pRoot2)
		{
			return true;
		}
		if(pRoot1->val!=pRoot2->val)
		{
			return false;
		}
		return isSame(pRoot1->left,pRoot2->left)&&isSame(pRoot1->right, pRoot2->right);
	}
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
		if(!pRoot1||!pRoot2)
		{
			return false;
		}
		return isSame(pRoot1,pRoot2)||HasSubtree(pRoot1->left, pRoot2)||HasSubtree(pRoot1->right, pRoot2);
	
    }
};

非递归法

• 重点：1.选择头节点 2从头节点开始比较
• 相比递归法，用bfs找头节点，再用bfs从头节点开始比较
• bfs比前中后序遍历可以避免子节点影响

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
#include <queue>
class Solution {
public:
	bool isSame(TreeNode* pRoot1,TreeNode* pRoot2)
	{
		queue<TreeNode*> q1;
		queue<TreeNode*>q2;
		q1.push(pRoot1);
		q2.push(pRoot2);
		while(q2.size())
		{
			if(q2.front())
			{
				if(!q1.front()||
				q2.front()->val!=q1.front()->val)
				{
					return false;
				}
				q2.push(q2.front()->left);
				q2.push(q2.front()->right);
				q1.push(q1.front()->left);
				q1.push(q1.front()->right);
			}
			q2.pop();
			q1.pop();

		}
		return true;
	}
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
		if(!pRoot1||!pRoot2)
		{
			return false;
		}
		queue<TreeNode* >q;
		q.push(pRoot1);
		while(q.size())
		{
			TreeNode* node=q.front();
			if(node)
			{
				if(isSame(node,pRoot2))
				{
					return true;
				}
				q.push(node->left);
				q.push(node->right);

			}
			q.pop();

		}
		return false;
    }
};