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

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