首页 > 代码库 > 字符串练习题（一）： 拓扑结构相同子树
字符串练习题（一）： 拓扑结构相同子树
对于两棵彼此独立的二叉树A和B，请编写一个高效算法，检查A中是否存在一棵子树与B树的拓扑结构完全相同。
给定两棵二叉树的头结点A和B，请返回一个bool值，代表A中是否存在一棵同构于B的子树。
/*public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/public class IdenticalTree { public boolean chkIdentical(TreeNode t1, TreeNode t2){ String t1Str = serialByPre(t1); String t2Str = serialByPre(t2); return getIndexOf(t1Str, t2Str) != -1; } //KMP private int getIndexOf(String s, String m) { if(s == null || m == null || m.length() < 1 ||s.length() < m.length()){ return -1; } char[] ss = s.toCharArray(); char[] ms = m.toCharArray(); int[] nextArr = getNextArray(ms); int index = 0; int mi = 0; while(index < ss.length && mi < ms.length){ if(ss[index] == ms[mi]){ index++; mi++; }else if(nextArr[mi] == -1){ index++; }else{ mi = nextArr[mi]; } } return mi == ms.length? index - mi: -1; } private static int[] getNextArray(char[] ms) { if(ms.length == 1){ return new int[]{-1}; } int[] nextArr = new int[ms.length]; nextArr[0] = -1; nextArr[1] = 0; int pos = 2; int cn = 0; while(pos < nextArr.length){ if(ms[pos - 1] == ms[cn]){ nextArr[pos++] = ++cn; }else if(cn > 0){ cn = nextArr[cn]; }else{ nextArr[pos++] = 0; } } return nextArr; } private String serialByPre(TreeNode head) { if(head == null){ return "#!"; } String res = head.val + "!"; res += serialByPre(head.left); res += serialByPre(head.right); return res; }}
字符串练习题（一）： 拓扑结构相同子树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。