题解 | #树的子结构#

class Solution {
public:
    bool Has_same(TreeNode* pRoot1,TreeNode* pRoot2) 
    {
        if(!pRoot2)return true;
        else if(!pRoot1||pRoot1->val!=pRoot2->val)return false;
        return Has_same(pRoot1->left,pRoot2->left)&&Has_same(pRoot1->right,pRoot2->right);
    }

    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if(!pRoot1||!pRoot2) return false;
        deque<TreeNode*>deq;
        TreeNode* pro=nullptr;
        deq.push_back(pRoot1);
        while(!deq.empty())
        {
            int time=deq.size();
            for(int i=0;i<time;i++)
            {
                pro=deq.front();
                if(Has_same(pro,pRoot2))    return true;    //访问,处理
                if(pro->left)deq.push_back(pro->left);      //下一个
                if(pro->right)deq.push_back(pro->right);
                deq.pop_front();                            //删除队首
            }
            // 下一行
        }
        return false;
    }
};

思路：

相等函数：判断 二叉树1 是否完全包含 二叉树2，头结点相等（利用深度优先遍历，递归法）

主函数： 判断 二叉树1 每一个节点是否和 二叉树2 相等（利用相等函数）（广度优先遍历，队列）