【力扣572】另一颗树的子树

• 题目
• 思路

1. 递归
2. 迭代，使用前序或者后序遍历将两棵树的节点储存在容器中，注意因为题目性质，需要子树完成相等而不是一部分相等，所以需要将每个叶节点的空孩子也表示出来；不能使用中序遍历，使用中序遍历的时候，错误如下:

== 子树根节点的右树的最左节点作为左树最右节点的后节点会造错误==

• code(迭代)

class Solution {
public:
    vector vec;
    vector nexts;
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        process(root);
        vector root_vec = vec;
        vec.clear();
        process(subRoot);
        vector sub_vec = vec;
        get_nexts(sub_vec);
        int ptr1 = 0;
        int ptr2 = 0;
        while(ptr1 < root_vec.size() && ptr2 < sub_vec.size())
        {
            if(root_vec[ptr1] == sub_vec[ptr2])
            {
                ptr1++;
                ptr2++;
            }
            else if(ptr2==0)
                ptr1++;
            else
                ptr2 = nexts[ptr2];
        }
        return ptr2 == sub_vec.size();
    }
    void get_nexts(vector vec)
    {
        int L = vec.size();
        if(L<1)
            return;
        nexts.resize(L+1);
        nexts[0] = -1;
        nexts[1] = 0;
        int cur_idx = 2;
        int cm = nexts[cur_idx-1];
        while(cur_idx<=L)
        {
            if(vec[cm] == vec[cur_idx-1])
                nexts[cur_idx++] = ++cm;
            else if(cm>0)
                cm = nexts[cm];
            else    
                nexts[cur_idx++] = 0;
        }
        return;
    }
    void process(TreeNode* root)
    {   
        if(root==nullptr)
        {
            vec.push_back(INT_MAX);
            return;
        }
        vec.push_back(root->val);
        process(root->left);
        process(root->right);

        return;
    }