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

Question

您好，我一直在做这件事，不知道该怎么做。

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

关于如何解决这个问题有什么想法吗？

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())