对于两棵彼此独立的二叉树A和B,请编写一个高效算法,检查A中是否存在一棵子树与B树的拓扑结构完全相同。
给定两棵二叉树的头结点A和B,请返回一个bool值,代表A中是否存在一棵同构于B的子树。
class IdenticalTree { public: //isSame递归验证A B树是否完全相等,有坑注意: //虽然题意说拓扑结构相同即可,但还是要验证 A->val == B->val bool isSame(TreeNode* A, TreeNode* B) { if(A==NULL && B==NULL)return true; else if(A==NULL || B==NULL) return false; else return (A->val == B->val) && isSame(A->left,B->left) && isSame(A->right,B->right); } //验证是否有子树和B相同 bool chkIdentical(TreeNode* A, TreeNode* B) { // write code here bool flag=isSame(A,B); if(flag) return true;//相同返回true else//不同则比较B是否和A的左右子树 { return ((A->left != NULL && chkIdentical(A->left,B)) || (A->right != NULL && chkIdentical(A->right,B))); } } };
递归,注意写递归时的退出情况。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class IdenticalTree {
public:
bool isSame(TreeNode* a,TreeNode* b){
if(a == NULL && b == NULL) return true;
if(a == NULL && b != NULL) return false;
if(a != NULL && b == NULL) return false;
if(a->val != b->val) return false;
else if(a->val == b->val){
return isSame(a->left,b->left) && isSame(a->right,b->right);
}
return true;
}
bool chkIdentical(TreeNode* A, TreeNode* B) {
// write code here
if(A==NULL) return false;
if(isSame(A,B)) return true;
else{
return chkIdentical(A->left,B) || chkIdentical(A->right,B);
}
}
};
void preOrder(TreeNode* t, string &s) { if(t != NULL) { s += ('0'+t->val); preOrder(t->left,s); preOrder(t->right,s); } else { s += '#'; // 缺失的叶子节点 } } bool chkIdentical(TreeNode* A, TreeNode* B) { if(A == NULL && B == NULL) return true; if(A&&B) { string sA,sB; preOrder(A,sA); preOrder(B,sB); if(sA.find(sB) != string::npos) return true; } return false; }
class IdenticalTree { public: bool Equal(TreeNode *A,TreeNode *B){ if(A==NULL && B==NULL) return true; else if(A==NULL || B==NULL) return false; else return (A->val==B->val) && Equal(A->left,B->left) && Equal(A->right,B->right); } bool chkIdentical(TreeNode* A, TreeNode* B) { if(Equal(A,B)) return true; else return (A->left!=NULL && chkIdentical(A->left,B)) || (A->right!=NULL && chkIdentical(A->right,B)); } };
class IdenticalTree {public:bool chkIdentical(TreeNode* A, TreeNode* B) {// write code hereif (A==NULL && B==NULL) return true;else if (A==NULL || B==NULL) return false;if(isIdentical(A, B)) return true;if(chkIdentical(A->left, B)) return true;if(chkIdentical(A->right, B)) return true;return false;}bool isIdentical(TreeNode* A, TreeNode* B){if (A==NULL && B==NULL) return true;else if (A==NULL || B==NULL) return false;if (A->val==B->val && isIdentical(A->left, B->left) && isIdentical(A->right, B->right)) return true;else return false;}};一定要确保终止条件,否则A或B为NULL时,会无限递归下去。
bool chkIdentical(TreeNode* A, TreeNode* B) { // write code here if(B == NULL) return true; if(A == NULL) return false; if(JudgeTopo(A, B)) return true; if(chkIdentical(A->left, B)) return true; if(chkIdentical(A->right, B)) return true; return false; } bool JudgeTopo(TreeNode* A, TreeNode* B){ if((A==NULL&&B) || (A&&B==NULL)) return false; if(A==NULL&&B==NULL) return true; return A->val==B->val&&JudgeTopo(A->left,B->left)&&JudgeTopo(A->right,B->right); }
public class IdenticalTree { public boolean chkIdentical(TreeNode A, TreeNode B) { if (A == null && B != null) { //这句不能掉,否则可能会抛出空指针异常 return false; } if (isIdentical(A, B)) { return true; } if (chkIdentical(A.left, B)) { return true; } else if (chkIdentical(A.right, B)) { return true; } return false; } public boolean isIdentical(TreeNode A, TreeNode B) { if (A == null && B == null) { return true; } if (A == null || B == null) { return false; } return A.val == B.val && isIdentical(A.left, B.left) && isIdentical(A.right, B.right); } }
class IdenticalTree { public: bool chkIdentical(TreeNode* A, TreeNode* B) { if (!A) return false; return isSameTree(A, B) || chkIdentical(A->left, B) || chkIdentical(A->right, B); } private: bool isSameTree(TreeNode* A, TreeNode* B) { if (!A || !B) return A == B; return A->val == B->val && isSameTree(A->left, B->left) && isSameTree(A->right, B->right); } };
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class IdenticalTree: def chkIdentical(self, A, B): # write code here def find(A,B): if not A and not B:#都为叶节点时则为相同 return True elif not A and B:#不同时为空则不同 return False elif A and not B: return False else:#都不为空时就要比较左子树和右子树 return find(A.left,B.left) and find(A.right,B.right) result=False if A and B: if A.val==B.val: result=find(A,B) if not result: result=self.chkIdentical(A.left,B) or self.chkIdentical(A.right,B) return result 参考的大佬的答案,做了一点修改
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class IdenticalTree: def chkIdentical(self, A, B): ans = False if A and B: if A.val==B.val: ans = self.help(A,B) if not ans:#AB当前根节点不等时,判断A的左、右子树是否等于B ans = self.chkIdentical(A.left,B) if not ans: ans = self.chkIdentical(A.right,B) return ans def help(self,a,b): if not a and not b:#a,b都为空,则已到达叶节点,且结构相同,返回true return True elif (a and not b) or (b and not a):#一个为空一个不为空,则结构不同,返回false return False return self.help(a.left,b.left) and self.help(a.right,b.right)#都不为空时,分别比较左右子树结构是否相同
这里提供一种思路,先把两棵树按照某种遍历方法转化为一维数组,然后看 B 树的转化结果是不是 A 树的子序列,如果是,那就是其子树。只要知道先序(或者后续)+中序就可以完全确定树。但是为了简化,我们可以把树的空节点也表示出来,这样就把两棵树转化成了满二叉树,这样就可以通过一次遍历完全得知这棵树的构建方法,在使用上述方法即可。
例如:(层遍历){1 1 1 # 1 1 #}{1 # 1}。转化为对应树为(设-99为NULL){1 1 -99 1 -99 1 1 -99 -99 -99}{1 -99 1 -99 -99},后一个数组明显是前一个的子数组,因此返回True。
参考代码如下:
class IdenticalTree { void getPrnt(TreeNode *tree, vector &vec) { if (tree == nullptr) { vec.push_back(-99); return; } vec.push_back(tree->val); getPrnt(tree->left, vec); getPrnt(tree->right, vec); } public: bool chkIdentical(TreeNode* A, TreeNode* B) { bool flag = false; vector mainTree, subTree; getPrnt(A, mainTree), getPrnt(B, subTree); for (int i = 0; i < mainTree.size(); i++) { int ptr1 = i, ptr2 = 0; while (ptr1 < mainTree.size() && ptr2 < subTree.size()) { if (mainTree[ptr1++] != subTree[ptr2++]) break; } if (ptr2 >= subTree.size() && mainTree[ptr1 - 1] == subTree[ptr2 - 1]) { flag = !flag; break; } } return flag; } };
//跟单纯找子树不同,需要A树也同时访问到叶节点
class IdenticalTree {
public:
bool core(TreeNode* cura,TreeNode* curb)
{
if(cura==nullptr&&curb==nullptr)
return true;
if(!cura||!curb)
return false;
return cura->val==curb->val&&core(cura->left,curb->left)&&core(cura->right,curb->right);
}
bool chkIdentical(TreeNode* A, TreeNode* B) {
// write code here
if(A==nullptr)
return false;
if(core(A,B))
return true;
return (chkIdentical(A->left,B))||(chkIdentical(A->right,B));
}
};
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class IdenticalTree { public: string serialize(TreeNode*A){ if(!A)return "#"; char buf[256]; snprintf(buf,sizeof(buf),"%d",A->val); return buf+serialize(A->left)+serialize(A->right); } bool chkIdentical(TreeNode* A, TreeNode* B) { string sA=serialize(A),sB=serialize(B); return sA.find(sB) != string::npos; } };