题解 | 树的子结构

/*
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 HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if (!pRoot1 || !pRoot2) return false;
        queue<TreeNode*> q;
        q.push(pRoot1);
        while (!q.empty()) {
            TreeNode* temp = q.front();
            q.pop();
            if (temp->left) q.push(temp->left);
            if (temp->right) q.push(temp->right);
            if (temp->val == pRoot2->val) {
                queue<TreeNode*>q1, q2;
                bool ans = true;
                q1.push(temp), q2.push(pRoot2);
                while (!q1.empty() && !q2.empty()) {
                    TreeNode* t1 = q1.front();
                    TreeNode* t2 = q2.front();
                    q1.pop(), q2.pop();
                    if (t1->val != t2->val) {
                        ans = false;
                        break;
                    };
                    if (t1->left&&t2->left) q1.push(t1->left);
                    if (t1->right&&t2->right) q1.push(t1->right);
                    if (t2->left) q2.push(t2->left);
                    if (t2->right) q2.push(t2->right);
                    if (q1.empty() && !q2.empty()) {
                        ans = false;
                        break;
                    }
                }
                if (ans)
                    return true;
            }
        }
        return false;
    }
};

方法一（二重层次遍历）：对每个A树层次遍历节点，然后看以这个节点为根节点的树对应B节点有的节点是否相等（再次使用层次遍历，这时一步一步完全对应）。

注意B树没有的节点A树可以有，但是它们不比较，也就不放入子级层次遍历的A树队列中。

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

    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if (pRoot1 == nullptr || pRoot2 == nullptr)return false;
        bool flag1 = false, flag2 = false, flag3 = false;
        if (pRoot1->val == pRoot2->val) {
            flag1 = checkOne(pRoot1, pRoot2);
        }
        flag2 = HasSubtree(pRoot1->left, pRoot2);
        flag3 = HasSubtree(pRoot1->right, pRoot2);
		//std::cout<<flag1<<" "<<flag2<<" "<<flag3<<std::endl;
        return flag1 || flag2 || flag3;
    }
};

方法二（迭代）：

因为处理顺序只需要两者一致就行，所以前序中序后序都可以。需要注意的点和方法一相同（二级时刻以B树为主体，因为A树有B树没有的部分（比如B树右节点为空而A树有）并不影响B树在A树中）。

两个方法都是双层遍历，一级遍历A树，二级（子级）遍历B树。因此只要是遍历就行，它们的遍历方法可以混着来，只要二级遍历A树和B树使用相同方法就行（目的是对应位置一致）。