树的同构:我理解的同构应该是树若干个结点平行交换形成与原树结构相同的树。但看到网上的一些实现都是认为树的同构必须是树的先序遍历是相同的。先贴上自己的代码。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class IdenticalTree {
public:
bool chkIdentical(TreeNode* A, TreeNode* B) {
// write code here
if(A==NULL||B==NULL)
{
return false;
}
string s1;
string s2;
s1=toTranslate(A);
s2=toTranslate(B);
if(string::npos!=s1.find(s2))return true;
return false;
}
string toTranslate(TreeNode *A)
{
if(A==NULL)return "#!";
string s;
s=to_string(A->val)+"!";
s+=toTranslate(A->left);
s+=toTranslate(A->right);
return s;
}
};
bool chkIdentical(TreeNode* A, TreeNode* B)
上面的函数就是比较A中是否存在一棵同构于B的子树。其实程序的结构为:对A、B分别进行先序遍历,求得其先序遍历序列。然后利用string类型的find()函数查找s1序列中是否囊括s2序列,由此判断出A中是否存在一棵同构于B的子树。记录一下几个知识点:
先序遍历:即某节点---->左子树----->右子树。采用递归来遍历输出先序序列。
string.find()函数: