题解 | #树的子结构#

涉及到两个迭代，分别树匹配树起点的迭代，以及匹配树和待匹配树的同步递归

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
  public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
      if (pRoot2 == nullptr) {
        return false;
      }
      if (pRoot1 == nullptr && pRoot2) {
        return false;
      }
      
      //  以当前起点进行进一步递归匹配
      bool flag1 = recursion(pRoot1, pRoot2);
      //  比较左子树和右子树，左右子树又是一颗独立的树
      //  以每个节点作为起点，进行每一轮的匹配
      bool flag2 = HasSubtree(pRoot1->left, pRoot2);
      bool flag3 = HasSubtree(pRoot1->right, pRoot2);
      
      return flag1 || flag2 || flag3;
    }
  private:
    bool recursion(TreeNode *root1, TreeNode *root2) {
      //  待匹配树不为空
      if (root1 == nullptr && root2) {
        return false;
      }
      
      //  待匹配树匹配到空成功，此时匹配树可空可不空
      if (root1 == nullptr || root2 == nullptr) {
        return true;
      }
      
      //  两个都有值，匹配是否相等
      if (root1->val != root2->val) {
        return false;
      }
      
      //  匹配一个成功，寻找下一个匹配
      return recursion(root1->left, root2->left) && recursion(root1->right, root2->right);
    }
};