对于两棵彼此独立的二叉树A和B,请编写一个高效算法,检查A中是否存在一棵子树与B树的拓扑结构完全相同。
思路:前序遍历二叉树(或者后序,因为这样子树的部分会集中在一起),然后变成字符串的包含匹配问题。
因为二叉树的遍历序列有二义性,例如
- A的左孩子是B,右为空
- A的右孩子是B,左为空
两者的遍历序列是一样的。为了消除这种情况,我们定义左右孩子为空的时候,分别在序列中添加特定的符号。
//用这种方式,在不断递归的函数中增长一个字符串
void go(TreeNode* h,string& v){
if(h){
v+=h->val;
if(h->left)
go(h->left,v);
else
v+='-';
if(h->right)
go(h->right,v);
else
v+='+';
}
}
bool chkIdentical(TreeNode* A, TreeNode* B) {
string s1,s2;
go(A,s1);
go(B,s2);
//kmp函数参见《算法:KMP算法》
int d=kmp(s1.c_str(),s2.c_str());
return d!=-1;
}