题解 | #树的子结构#

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
#include <cstddef>
class Solution {
public:
	bool recursion(TreeNode* root1,TreeNode* root2){
		if(root1==NULL&&root2!=NULL){
			return false;
		}
		if(root1==NULL||root2==NULL){
			return true;
		}
		if(root1->val!=root2->val){
			return false;
		}
		return recursion(root1->left,root2->left)&&recursion(root1->right, root2->right);
	}
	//对A树的每一个节点，都同步遍历查看是否匹配B树,类似字符串匹配的暴力解法
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
		if(pRoot2==NULL||pRoot1==NULL){
			return false;
		}
		bool flag1=recursion(pRoot1, pRoot2);
		bool flag2=HasSubtree(pRoot1->left, pRoot2);
		bool flag3=HasSubtree(pRoot1->right, pRoot2);
		return flag1||flag2||flag3;
    }
};

对于树的问题用递归解法的话，只需要考虑根节点，左孩子，有孩子，然后再去思考题目对这三个节点所需要采取的措施。