题解 | 树的子结构

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
	


public:
	bool HasSubTreeHelper(TreeNode* pRoot1, TreeNode* pRoot2) {
		if (pRoot1 == nullptr && pRoot2 != nullptr)
			return false;
		if (pRoot1 == nullptr || pRoot2 == nullptr)
			return true;
		if (pRoot1->val != pRoot2->val)
			return false;


		return HasSubTreeHelper(pRoot1->left, pRoot2->left) && HasSubTreeHelper(pRoot1->right, pRoot2->right);
	}
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {

		if (pRoot2 == nullptr)
			return false;
		if(pRoot1 == nullptr && pRoot2 != nullptr)
            return false;
        if(pRoot1 == nullptr || pRoot2 == nullptr)
            return true;
		bool middle = HasSubTreeHelper(pRoot1, pRoot2);

		bool leftcmp = HasSubtree(pRoot1->left, pRoot2);
		bool rightcmp = HasSubtree(pRoot1->right, pRoot2);

		return leftcmp || middle || rightcmp;
		//空树
        // if(pRoot2 == NULL)
        //     return false;
        // //一个为空，另一个不为空
        // if(pRoot1 == NULL && pRoot2 != NULL)
        //     return false;
        // if(pRoot1 == NULL || pRoot2 == NULL)
        //     return true;
        // //递归比较
        // bool flag1 = HasSubTreeHelper(pRoot1, pRoot2); 
        // //递归树1的每个节点
        // bool flag2 = HasSubtree(pRoot1->left, pRoot2); 
        // bool flag3 = HasSubtree(pRoot1->right, pRoot2);
        // return flag1 || flag2 || flag3;
    }


};





///
// TreeNode* currRt1 = pRoot1;
		// TreeNode* currRt2 = pRoot2;
		// //empty tree is not the subtree of any
		//  if (currRt2 == NULL)
		// 	return false;

		// // if (currRt1->left == NULL && currRt1->right == NULL && currRt2->left == NULL && currRt2->right == NULL) {
		// // 	if (currRt1->val == currRt2->val)
		// // 		return true;
		// // 	else
		// // 	 	return false;
		// // }


		// if (currRt1->val != currRt2->val) {
		// 	if (currRt1->right == NULL && currRt1->left == NULL) 
		// 		return false;
		// 	else {
		// 		if (currRt1->left != NULL && currRt1->right != NULL)
		// 		return HasSubtree(currRt1->left, currRt2) || HasSubtree(currRt1->right, currRt2);
		// 		else if (currRt1->left == NULL && currRt1->right != NULL)
		// 			return HasSubtree(currRt1->right, currRt2);
		// 		else //if (currRt1->left != NULL && currRt1->right == NULL)
		// 			return HasSubtree(currRt1->right, currRt2);
		// 	}
			
			
		// } else {
		// 	if (currRt2->left != NULL && currRt1->left == NULL || currRt2->right != NULL && currRt1->right == NULL)
		// 		return false;
		// 	else {
		// 		if (currRt2->left == NULL && currRt2->right == NULL)
		// 			return true;
		// 		else {
		// 			if (currRt2->left == NULL && currRt2->right != NULL ) 
		// 				return HasSubtree(currRt1->right, currRt2->right);
		// 			else //if (currRt2->right == NULL && currRt2->left != NULL) 
		// 				return HasSubtree(currRt1->left, currRt1->left);
		// 		}
		// 	}
		// }

递归首先要明确base case。最明显的一个是pRoot2==nullptr,然后就是在pRoot1遍历完的时候pRoot2还没有遍历完返回false，唯有pRoot2和pRoot1(排除前面的情况之后)有一个都遍历完了或者pRoot2先遍历完的情况下返回true，然后再加上对应的递归#剑指offer#