二叉树的问题。检查类似的形状 [英] Binary Trees question. Checking for similar shape

问题描述

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

Hi I'm stuck doing this, not sure how to go about it.

如果我有两个二叉树，我将如何检查是否具有相同的形状？在节点的数据也没有关系，只是如果树结构是相等的。

If I have two binary trees, how would I check if the have the same shape? Data in the nodes doesn't matter, just if the tree structures are equal.

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

Any ideas on how to solve this problem?

推荐答案

您可以轻松地做到这一点与递归。此以下code可行的，因为两个非空树具有相同的形状，当且仅当它们各自的子树具有相同的形状

You can easily do that with recursion. This following code works because two non-empty trees have the same shape if and only if their respective subtrees have the same shape.

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

要检查两棵树，通过他们的根节点的功能上面。

To check two trees, pass their root nodes to the function above.

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

这篇关于二叉树的问题。检查类似的形状的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！