可能是重复问题：
确定两个二叉树是否相等
昨天参加了面试，有一个问题让我很困惑，问题如下：
描述
有
2 个二叉树，请检查它们是否相等。只有当
tree1->child == tree2->child，且其中一个树的左右子节点可以相互交换时，它们才相等。
例如：
5 6
/ \ / \ they are equal.
1 2 2 1
5 6
/ \ / \ they are equal.
1 2 2 1
/ \ / /
3 4 4 3
非常感谢您的建议。
等于运算符是可传递的：如果A=B，B=C，则A=B=C，因此A=C。
等于运算符是自反的：无论它们的值如何，A=A，B=B和C=C。
等于运算符是对称的。如果A=B，则B=A。（它们的顺序无关紧要。）
现在，看一下他们给你的定义：
如果子节点相等，则树等于另一个树。我们可以假设在底部比较节点，否则定义就没什么用了。但是他们没有告诉你如何解决比较，整个定义都取决于它。
简而言之，这是一个糟糕的问题。
但是，让我们看看如果我们决定尝试解开这个问题会发生什么。
但是，请等一下，他们还告诉你任何树的两个子节点都可以交换。这增加了一个约束条件，即任何与其他任何东西（包括它本身）相等的树必须等于其镜像。以及其子树的任何变化。
并且请记住，这应该是一个搜索树。因此，我们可以假设由同一算法处理的两个不同搜索树如果相等，则必须给出相同的结果。因此，如果我们交换树的元素，则搜索时间会受到影响。因此，没有每个节点都在其位置上的树彼此不相等。
将其与此等式的“可互换”性质结合起来，我们可以看到这不是一个有效的等式定义。（如果我们尝试应用它，那么结果只有具有特定级别每个节点的相同节点的树才相等，并且仅相等于它们自己，这违反了等于运算符的自反性部分。）
tree1->child和tree2->child也没有定义清楚。这是他们措辞不当的错误，因为一个节点不只有一个子节点。 - ninjageckoA=A 并不总是成立的，例如 nan != nan。 - jfs我认为这不是一个不合理的问题。一个简单的递归解决方案是
boolean equals(x, y)
{
if (x == null)
{
return y == null;
}
if (y == null)
{
return false;
}
if (x.val != y.val)
{
return false;
}
if (equals(x.left, y.left) && equals(x.right, y.right))
{
return true;
}
if (equals(x.left, y.right) && equals(x.right, y.left))
{
return true;
}
return false;
}
child视为节点对象的集合，则可能是有效的...我曾经使用一堆Map和List对象递归地实现了一棵树，每个节点的子节点都存储在一个列表中，该列表由字符串“child”映射到节点。 - user684934.children（就像我在答案中所做的那样）。 - ninjagecko使用@mcdowella建议的规范化方法来比较树。不同之处在于，我的方法不需要与树中节点数量成比例的O(N)额外内存：
# in Python
from collections import namedtuple
from itertools import chain
# Tree is either None or a tuple of its value and left, right trees
Tree = namedtuple('Tree', 'value left right')
def canonorder(a, b):
"""Sort nodes a, b by their values.
`None` goes to the left
"""
if (a and b and a.value > b.value) or b is None:
a, b = b, a # swap
return a, b
def canonwalk(tree, canonorder=canonorder):
"""Yield all tree nodes in a canonical order.
Bottom-up, smaller children first, None is the smallest
"""
if tree is not None:
children = tree[1:]
if all(t is None for t in children): return # cut None leaves
children = canonorder(*children)
for child in chain(*map(canonwalk, children)):
yield child
yield tree
canonwalk()需要执行O(N*M)步骤和使用O(log(N)*M)内存来返回树中的所有节点，其中N是节点总数，M是每个节点拥有的子节点数量（对于二叉树，它为2）。
canonorder()可以轻松地推广到任何节点表示和任意子节点数量。 canonwalk()仅需要一棵树可以访问其直接子节点作为序列。
调用canonwalk()的比较函数：
from itertools import imap, izip_longest
unset = object()
def cmptree(*trees):
unequal = False # allow root nodes to be unequal
# traverse in parallel all trees under comparison
for nodes in izip_longest(*imap(canonwalk, trees), fillvalue=unset):
if unequal:
return False # children nodes are not equal
if any(t is unset for t in nodes):
return False # different number of nodes
if all(t is not None for t in nodes):
unequal = any(nodes[-1].value != t.value for t in nodes)
else: # some are None
unequal = any(t is not None for t in nodes)
return True # equal
5 6
/ \ / \ they are equal.
1 2 2 1
/ \ / /
3 4 4 3
tree1 = Tree(5,
Tree(1,
Tree(3, None,None), None),
Tree(2,
None, Tree(4, None, None)))
tree2 = Tree(6,
Tree(2, Tree(4, None, None), None),
Tree(1, Tree(3, None, None), None))
print cmptree(tree1, tree2)
True
在Ruby中不使用递归的解决方案
def same? top_t1, top_t2
for_chek << [top_t1, top_t2] # (1) put task for check into queue
while t1,t2 = for_check.shift # (2)
return false unless t1.children.count == t2.children.count # generally for non-binary tree, but also needed for controlling of nil children
break if t1.children.empty?
t1_children = t1.children.sort # this is sorted arrays
t2_children = t2.children.sort # of childrens
return false unless t1_children == t2_children # (3)
0.upto(t1_children.count - 1) do |i|
for_check << [t1_children[i], t2_children[i]] # put equivalent child pairs into queue
end
end
return true
end
Ruby语法提示：
arr << elem；在这种情况下，for_check是一个数组的数组t1,t2 = [item1, item2]。与arr = [item1, item2]; t1 = arr[0]; t2 = arr[1]相同t1_children == t2_children假定对于这种对象，==具有相应的行为。更详细的写法是t1_children.map { |el| el.val } == t2_children.map { |el| el.val } - 这里map生成val的数组。
你给的链接是重复的，在我的问题中，一棵树的左/右子节点可以交换，然后与另一棵树相等进行比较。 - Alcott