对于两棵彼此独立的二叉树A和B,请编写一个高效算法,检查A中是否存在一棵子树与B树的拓扑结构完全相同。
给定两棵二叉树的头结点A和B,请返回一个bool值,代表A中是否存在一棵同构于B的子树。
解题思路:
1.我们可以对于A树的每一个节点,进行判断,看是否和B相等,但是这样的时间复杂度为O(M*N),设A的节点数为M,B的节点数为N。
2.另外一种思路就是,我们先把两个树序列化,然后判断strA是否含有strB的子串,判断子串的时候,我们采用KMP算法,这样时间复杂度就可以降为O(M+N)。其中,我们需要采用前序遍历(或后序遍历),确保子树的序列化是连续的。中序遍历会由于插入中间值,导致序列化后不一致。
3.序列化的时候,我们需要对空的叶子节点进行插入特殊符号(数值)操作,这是用于判断只有一个叶子节点的节点的结构,如:
//需要加上叶子节点,加上叶子节点是为了判断当某个节点只有一个叶子节点时,能够知道是左孩子还是右孩子
//如–A—–A
//—/———-\
//–B———-B
//如树1,A的左节点为B,右节点为空
//树2,A的做节点为空,右节点为B
//如果不加叶子节点,那么前序遍历均为AB
//加上叶子节点后,分别为AB###和A#B##,可以判断
AC代码:
//需要加上叶子节点,加上叶子节点是为了判断当某个节点只有一个叶子节点时,能够知道是左孩子还是右孩子 //如 A A // / \ // B B //如果不加叶子节点,那么前序遍历均为AB //加上叶子节点后,分别为AB###和A#B##,可以判断 /* 对于两棵彼此独立的二叉树A和B,请编写一个高效算法,检查A中是否存在一棵子树与B树的拓扑结构完全相同。 给定两棵二叉树的头结点A和B,请返回一个bool值,代表A中是否存在一棵同构于B的子树 */ //前序遍历+KMP /* 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 (B == NULL) return true; else if (A == NULL) return false; vector<int> pattern; vector<int> str; dfs(A, str); dfs(B, pattern); if (str.size()<pattern.size()) return false; //构建next数组 vector<int> next(pattern.size() + 1, 0); for (int i = 1; i<pattern.size(); ++i) { int j = next[i]; while (j>0 && pattern[i] != pattern[j]) j = next[j]; if (pattern[i] == pattern[j]) next[i + 1] = j + 1;//求next[i+1]的值,所以比较的是p[i]和p[j] } //使用KMP int j = 0; for (int i = 0; i<str.size(); ++i) { while (j>0 && str[i] != pattern[j]) j = next[j]; if (str[i] == pattern[j]) j++;//比较下一个值 if (j == pattern.size()) { //匹配到字串了,返回真 return true; } } //没找到,false return false; } //进行前序遍历 void dfs(TreeNode* root, vector<int>&preOrder) { if (root == NULL){ //需要加上叶子节点,加上叶子节点是为了判断当某个节点只有一个叶子节点时,能够知道是左孩子还是右孩子 //如 A A // / \ // B B //如果不加叶子节点,那么前序遍历均为AB //加上叶子节点后,分别为AB###和A#B##,可以判断 preOrder.push_back(INT_MAX); return; } preOrder.push_back(root->val); dfs(root->left, preOrder); dfs(root->right, preOrder); } };