二叉树问题.检查相似的形状 [英] 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?

推荐答案

您可以使用递归轻松地做到这一点.以下代码有效，因为当且仅当它们各自的子树具有相同的形状时，两个非空树具有相同的形状.

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屋！