[basic_recursion]树的子结构

思路：

1.一开始马上想到的是KMP的思路关注点在加速匹配上，但树形结构好像很麻烦于是考证转化为数组存储是否可以匹配，因为数组的二叉树靠下表的2倍关系确定前后节点，所以这个思路好像是可行的，但想了一下要是稀疏树那数组的长度是指数级想想可怕就转去其他思路（但不代表这是不可行的，后来输出样例也是数组输出）
2.还想着KMP用二叉链存储，那怎么查看匹配子树的头尾是否有重合，好像也是要顺序查下来，或者逆序也是要顺序递归比树，为了加速匹配省去一个一个遍历查找才用这种，结果这种的子步骤本身也要遍历查找，放弃了（可能还是有方法的）
3.用二叉树递归查找了，一开始思考状态转移时走了个岔路，f（）：1两个树根相同则返回真，2若树根不同则树根的左右子树根分别和匹配调用f（）的结果；好像是这样，但后来才发现里面一个漏洞，这样定义f有两个通路，1为真时剩下的子树很自然的以为是同样的子节点调用f（）匹配，两子树根节点也相同则返回真，但f为真除了根相同还有跟不同但根的子树根和匹配树相同，则跟相同，子树根不同，但子树根的子树根和匹配树子树相同也会返回真，但这样的匹配是不连续的。问题出在f（）的定义B包含在A：1.A，B两棵树在此根节点开始相同，2.B包含（即又回到f（））在A的左或右子树，f（）的通路还是两条，但1的情况和f（）是完全分隔开的，那个漏洞就是1的递归没和f分隔。
4.又快速写了个遍历的，层次遍历。

#include <iostream>
#include <deque>
using namespace std;

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

//14:01--15：00--17:09--18:12
class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        return ContainSub_Recursion(pRoot1, pRoot2);
    }

    bool SameTree(TreeNode *root1, TreeNode *root2){  //以为是两棵树完全判同，其实是左树的一部分同右树
        if(root2 == NULL)  //对照树为空则左边什么节点都不用理
            return true;
        else if(root1 == NULL)   //对照树不为空的基础上，则左边为空就是不匹配
            return false;
        return (root1->val == root2->val) && SameTree(root1->left, root2->left) && SameTree(root1->right, root2->right);  //两边都非空
    }

    bool ContainSub_Recursion(TreeNode *root1, TreeNode *root2){
        if(root1 == NULL || root2 == NULL)
            return false;
        return SameTree(root1, root2) || ContainSub_Recursion(root1->left, root2) || ContainSub_Recursion(root1->right, root2);
    }

    bool ContainSub_ForEach_Layer(TreeNode *root1, TreeNode *root2){
        if(root1 == NULL || root2 == NULL)
            return false;
        deque<TreeNode*> d;
        d.push_back(root1);
        while(d.size()){
            if(d.front()->left)
                d.push_back(d.front()->left);
            if(d.front()->right)
                d.push_back(d.front()->right);
            if(SameTree(d.front(), root2))
                return true;
            else
                d.pop_front();
        }
        return false;
    }
};

int main() {
    Solution s;
    TreeNode *a = new TreeNode(8);
    a->left = new TreeNode(8);
    a->right = new TreeNode(7);
    a->left->left = new TreeNode(9);
    a->left->right = new TreeNode(2);
    a->left->right->left = new TreeNode(4);
    a->left->right->right = new TreeNode(7);

    TreeNode *b = new TreeNode(8);
    b->left = new TreeNode(9);
    b->right = new TreeNode(2);
    cout<<s.HasSubtree(a, b);

    return 0;
}