Check if a Tree is Isomorphic or Not in Java?

树的同构是树数据结构中的一个基本概念。如果一棵树可以通过交换某些节点的左右子节点来转换为另一棵树，则称这两棵树是同构的。

这意味着这两棵树必须具有相同的结构，但子节点的顺序可能不同。在本节中，我们将探讨同构树的属性、它们的特征，以及一种使用Java递归检查同构的有效方法。

什么是同构树？

如果一棵树可以通过在某些节点上交换左右子节点来转换为另一棵树，同时保持相同的结构，则称这两棵树是同构的。同构不考虑节点的实际值，只考虑它们的层级结构。

例如，考虑以下树

示例 1：同构树

树 1 和树 2 具有相同的结构，因为通过修改某些节点之间左右子节点的顺序，树 2 可以转换为树 1。

示例 2：非同构树

在这里，树 1 和树 2 不是同构的，因为它们的结构不同。

同构树的特征

1. 相同的结构：如果两棵树完全相同，则它们显然是同构的。
2. 子节点交换：即使在任意数量的节点上交换左右子节点，树仍然是同构的。
3. 节点计数约束：两棵树必须具有相同数量的节点才能成为同构。
4. 子树同构：如果一棵树的左子树与另一棵树的右子树匹配（或反之），它们仍然是同构的。

方法：使用递归检查树同构

递归方法比较两棵树的相应节点，并检查交换左右子节点是否使它们相同。步骤如下：

算法步骤

1. 基本情况

• 如果两棵树都为空（null），则返回 true（两者都显然是同构的）。
• 如果只有一棵树为空，而另一棵树不为空，则返回 false（它们不可能是同构的）。
• 如果当前节点的数据不匹配，则返回 false。

2. 递归检查

• 递归检查不交换子节点

• 递归检查交换子节点

最终条件

• 如果上述任一递归条件为 true，则返回 true。否则，返回 false。

文件名：IsomorphicTreeChecker.java

输出

 
The trees are isomorphic.   

代码说明

提供的 Java 应用程序通过一棵树可以转换为另一棵树来确定两棵 二叉 树是否具有同构关系，通过重新分配左右分支上的节点。

树节点的结构在 Node 类定义中出现。isIsomorphic() 函数使用递归来比较两棵树中的节点。它首先处理基本情况（空树、节点值不匹配），然后检查是否交换子节点后的同构性。 main 方法 构建了两棵树并调用 isIsomorphic()，打印它们是否同构。这种方法确保了 O(N) 的高效复杂度，使其适用于树结构比较。

复杂度分析

时间复杂度：O(N) - 每个节点都会被访问一次。

空间复杂度：O(H) - 取决于树的高度（递归深度）。

结论

树的同构是树结构比较中的一个关键概念。Java 提供了一种递归且高效的方法来确定两棵树是否同构。这种方法有助于涉及树数据结构的应用，例如编译器语法树、网络拓扑比较和数据库模式转换。理解树的同构对于改进算法问题解决中的树操作技术至关重要。