左神算法：判断 t1 树中是否有与 t2 树拓扑结构完全相同的子树（Java版）

本题来自左神《程序员代码面试指南》“判断 t1 树中是否有与 t2 树拓扑结构完全相同的子树”题目。

题目

给定彼此独立的两棵树头节点分别为 t1 和 t2，判断 t1 中是否有与 t2 树拓扑结构完全相同
的子树。
例如，如图3-36 所示的 t1 树和如图 3-37 所示的 t2 树。

题解

如果 t1 的节点数为 N，t2 的节点数为 M，则本题最优解是时间复杂度为O(N+M)的方法。

首先简单介绍一个时间复杂度为O(N×M)的方法：

对于 t1 的每棵子树，都去判断是否与 t2 树的拓扑结构完全一样，这个过程的时间复杂度为O(M)，t1 的子树一共有 N 棵，所以时间复杂度为O(N×M)，这种方法在本文中不再详述。

下面重点介绍一下时间复杂度为O(N+M)的方法：

首先把 t1 树和 t2 树按照先序遍历的方式序列化，关于这个内容，请阅读“二叉树的序列化和反序列化”问题。以题目的例子来说，t1 树序列化后的结果为“1!2!4!#!8!#!#!5!9!#!#!#!3!6!#!#!7!#!#!”，记为t1Str。t2 树序列化后的结果为“2!4!#!8!#!#!5!9!#!#!#!”，记为 t2Str。

接下来，只要验证 t2Str 是否是 t1Str 的子串即可，这个用 KMP 算法可以在线性时间内解决。

因此，t1 序列化的过程为 O(N)，t2 序列化的过程为 O(M)，KMP 解决 t1Str 和 t2Str 的匹配问题 O(M+N)，所以时间复杂度为 O(M+N)。

有关 KMP 算法的内容，请读者阅读“KMP 算法”问题，关于这个算法非常清晰的解释，这里不再详述。

代码

含测试用例

package chapter_3_binarytreeproblem;public class Problem_12_T1SubtreeEqualsT2 {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}public static boolean isSubtree(Node t1, Node t2) {String t1Str = serialByPre(t1);String t2Str = serialByPre(t2);return getIndexOf(t1Str, t2Str) != -1;}public static String serialByPre(Node head) {if (head == null) {return "#!";}String res = head.value + "!";res += serialByPre(head.left);res += serialByPre(head.right);return res;}// KMPpublic static 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;}public 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;}public static void main(String[] args) {Node t1 = new Node(1);t1.left = new Node(2);t1.right = new Node(3);t1.left.left = new Node(4);t1.left.right = new Node(5);t1.right.left = new Node(6);t1.right.right = new Node(7);t1.left.left.right = new Node(8);t1.left.right.left = new Node(9);Node t2 = new Node(2);t2.left = new Node(4);t2.left.right = new Node(8);t2.right = new Node(5);t2.right.left = new Node(9);System.out.println(isSubtree(t1, t2));}} 超强干货来袭 云风专访：近40年码龄，通宵达旦的技术人生

总结

以上是生活随笔为你收集整理的左神算法：判断 t1 树中是否有与 t2 树拓扑结构完全相同的子树（Java版）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。