題目
對(duì)于兩棵彼此獨(dú)立的二叉樹(shù)A和B早直，請(qǐng)編寫(xiě)一個(gè)高效算法，檢查A中是否存在一棵子樹(shù)與B樹(shù)的拓?fù)浣Y(jié)構(gòu)完全相同如输。
給定兩棵二叉樹(shù)的頭結(jié)點(diǎn)A和B有鹿，請(qǐng)返回一個(gè)bool值旭旭，代表A中是否存在一棵同構(gòu)于B的子樹(shù)。
思路
- 序列化二叉樹(shù)變成字符串
- 利用字符串算法中的KMP算法進(jìn)行模式匹配
- 時(shí)間復(fù)雜度為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數(shù)組
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;
}
// 匹配過(guò)程
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;
}
}
// ------------ 序列化二叉樹(shù) -----------------
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;
}
}
};
