你好我坚持这样做,不知道如何去做。
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())