토폴로지 구조 동일 서브트리 연습 문제

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

class IdenticalTree {
public:
    // ------- KMP  ------
    //  next 
    int* getNext(char* A, int lengthA) {
        int* next = new int[lengthA];
        next[0] = -1;
        int k = -1;
        int j = 0;
        while (j < lengthA - 1) {
            if (k == -1 || A[k] == A[j]) {
                k++;
                j++;
                if (A[k] == A[j]) {
                    next[j] = next[k];
                } else {
                    next[j] = k;
                }
            } else {
                k = next[k];
            }
        }
        return next;
    }
    
    //  
    int KMPMatch(char* A, int lengthA, char* B, int lengthB) {
        int i = 0;
        int j = 0;
        int* next = getNext(B, lengthB);
        while (i < lengthA && j < lengthB) {
            if (A[i] == B[j] || j == -1) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j == lengthB) {
            return i - j;
        } else {
            return -1;
        }
    }
    
    // ------------   -----------------
    void serilization(TreeNode *treeNode, vector &vector) {
        if (treeNode == NULL) {
            vector.push_back('#');
            return;
        }
        vector.push_back((char)(treeNode->val + 48));
        serilization(treeNode->left, vector);
        serilization(treeNode->right, vector);
    }
    
    bool chkIdentical(TreeNode* A, TreeNode* B) {
        // write code here
        vector vectorA;
        vector vectorB;
        serilization(A, vectorA);
        serilization(B, vectorB);
        char *charA = new char[vectorA.size()];
        char *charB = new char[vectorB.size()];
        for(int i = 0; i < vectorA.size(); i++) {
            charA[i] = vectorA[i];
        }
        for(int i = 0; i < vectorB.size(); i++) {
            charB[i] = vectorB[i];
        }
        if(KMPMatch(charA, (int)vectorA.size(), charB, (int)vectorB.size()) == -1) {
            return false;
        } else {
            return true;
        }
    }
};