本文共 786 字,大约阅读时间需要 2 分钟。
题目传送门://
题目描述
对于两棵彼此独立的二叉树A和B,请编写一个高效算法,检查A中是否存在一棵子树与B树的拓扑结构完全相同。
给定两棵二叉树的头结点A和B,请返回一个bool值,代表A中是否存在一棵同构于B的子树。
时间复杂度为O(N+M);
AC 代码
struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { }};class IdenticalTree { string getTreeStr(TreeNode *t){ if(!t) return "!"; string res; char p[15]; sprintf(p,"%d!",t->val); res+=p; res+=getTreeStr(t->left); res+=getTreeStr(t->right); return res; }public: bool chkIdentical(TreeNode* A, TreeNode* B) { string str1 = getTreeStr(A),str2 = getTreeStr(B); int pos =(int)str1.find(str2); if(pos==-1) return false; else return true; }};
转载地址:http://shhji.baihongyu.com/