屏幕快照 2017-09-06 下午8.35.16.png
問題
對于兩棵彼此獨(dú)立的二叉樹A和B频丘，請編寫一個(gè)高效算法过椎，檢查A中是否存在一棵子樹與B樹的拓?fù)浣Y(jié)構(gòu)完全相同忽肛。
給定兩棵二叉樹的頭結(jié)點(diǎn)A和B，請返回一個(gè)bool值保屯，代表A中是否存在一棵同構(gòu)于B的子樹秉版。
序列化用了遞歸和非遞歸闹司，字符串匹配一種是調(diào)用了string自帶的find函數(shù)，一種是自己寫的沐飘，KMP算法還不會……
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class IdenticalTree {
public:
// 廣度優(yōu)先,序列化樹,前序遍歷
void serialize_tree(TreeNode* A, string &serial)
{
stack<TreeNode*> q;
q.push(A);
while(!q.empty()){
TreeNode* curr = q.top();
q.pop();
if(curr){
serial += to_string(curr->val) + "!";
q.push(curr->right);
q.push(curr->left);
}else{
serial += "#!";
}
}
}
// 前序遍歷游桩，遞歸
void serialize_tree_R(TreeNode* A, string &serial)
{
if(!A){
serial += "#!";
return;
}
serial += to_string(A->val) + "!";
serialize_tree_R(A->left, serial);
serialize_tree_R(A->right, serial);
}
// 常規(guī)字符串匹配，O(N*M)
bool compare_str(string A, string B)
{
for(int i=0; i<=(A.size()-B.size()); ++i){
if(A.substr(i, B.size()) == B){
return true;
}
}
return false;
}
bool chkIdentical(TreeNode* A, TreeNode* B) {
// write code here
string a, b;
// 廣度優(yōu)先耐朴，前序遍歷借卧，非遞歸
// serialize_tree(A, a);
// serialize_tree(B, b);
// 前序遍歷，遞歸
serialize_tree_R(A, a);
serialize_tree_R(B, b);
// 用自帶的find函數(shù)查找
// return a.find(b) == string::npos ? false : true;
// 用自己寫的常規(guī)字符串匹配查找
return compare_str(a, b);
}
};
