拓扑结构相同子树练习题

题目

对于两棵彼此独立的二叉树A和B，请编写一个高效算法，检查A中是否存在一棵子树与B树的拓扑结构完全相同。

给定两棵二叉树的头结点A和B，请返回一个bool值，代表A中是否存在一棵同构于B的子树。

思路

• 序列化二叉树变成字符串
• 利用字符串算法中的KMP算法进行模式匹配
• 时间复杂度为O(M+N)

答案

/*
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<char> &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<char> vectorA;
        vector<char> 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;
        }
    }
};