二叉树问题。 检查相似的形状

嗨，我坚持这样做，不知道如何去做。

如果我有两个二叉树，我如何检查它是否具有相同的形状？ 只要树结构相等，节点中的数据无关紧要。

关于如何解决这个问题的任何想法？

Answer 1

您可以通过递归轻松完成此操作。 以下代码有效，因为当且仅当它们各自的子树具有相同的形状时，两个非空树具有相同的形状。

boolean equalTrees(Node lhs, Node rhs) { // Empty trees are equal if (lhs == null && rhs == null) return true; // Empty tree is not equal to a non-empty one if ((lhs == null && rhs != null) || (lhs != null && rhs == null)) return false; // otherwise check recursively return equalTrees(lhs.left(), rhs.left()) && equalTrees(lhs.right(), rhs.right()) } 

要检查两棵树，请将其根节点传递给上面的函数。

 equalTrees(tree1.root(), tree2.root()) 

Answer 2

并行的两个广度优先搜索将是一种方式。

http://en.wikipedia.org/wiki/Breadth-first_search

使用BFS，您可以同时检查树的特定级别的所有节点。 这样，如果你不区分右边和左边的孩子（即如果你的树被认为是相同的，如果一个节点的对手有一个孩子，不管“正确”或“左”孩子）你可以在那时处理。

Answer 3

如果我有两个二叉树，我如何检查它是否具有相同的形状？

您将很高兴知道二叉树具有一个有趣的属性： 它们可以表示为数组 。 只需将每个树转换为其中一个数组并比较数组内容即可。 空白单元格对应于不存在的左或右子节点，定义树的结构。 您希望迭代两个数组并确保在一个数组中遇到的每个空单元格出现在另一个数组中; 这是O（n）。

当然，如果数组大小不同，则根本不需要做任何工作，因为具有不同数量节点的树不可能具有相同的结构。 从那里开始，你们都完成了。

Answer 4

使用符号名称而不是实际数据按预先顺序和按顺序遍历它们，并比较生成的字符串。 也许你的数据结构上的更多输入将是有用的。

不是java相关的AFAICT

Answer 5

只需按照树枝，模仿另一棵树中的每一个动作。 在Python伪代码中：

类树：
     def __init __（self，value，left = None，right = None）：
         self.value = value
         self.left = left
         self.right =对

 def same_shape（T1，T2）：
    如果T1 ==无：
        返回T2 ==无

    如果T2 ==无：
        返回T1 ==无

    返回same_shape（T1.left，T2.left）和same_shape（T1.right，T2.right）