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

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