题解 | #树的子结构#

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
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);
    }
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        //空树
        if(pRoot2 == NULL)
            return false;
        //一个为空，另一个不为空
        if(pRoot1 == NULL && pRoot2 != NULL)
            return false;
        if(pRoot1 == NULL || pRoot2 == NULL)
            return true;
        //递归比较
        bool flag1 = recursion(pRoot1, pRoot2); 
        //递归树1的每个节点
        bool flag2 = HasSubtree(pRoot1->left, pRoot2); 
        bool flag3 = HasSubtree(pRoot1->right, pRoot2);
        return flag1 || flag2 || flag3;
    }
};

两层前序遍历，第一层前序遍历遍历树A，判断每个根节点对应的子树和树B一不一样。第二层前序遍历用来具体判断两个树是不是完全一样。