2个二叉树是否相等

Question

可能的重复：
判断两个二叉树是否相等

昨天面试，一道题明白了，这是：

描述

有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

任何想法都会受到赞赏。

Answer 1

等式运算符具有传递性：如果 A=B，且 B=C，则 A=B=C，因此 A=C。

相等运算符是自反的：A=A、B=B 和 C=C，无论它们的值是什么。

等式运算符是对称的。如果A=B，则B=A。 （它们的顺序并不重要。）

现在，看一下他们给您的定义：

如果子树相等，则一棵树与另一棵树相等。让我们来看看。我们可以假设节点是在底部进行比较的，否则这个定义就毫无用处。但他们懒得告诉你如何解决这种比较，他们给你的整个定义取决于它。

简而言之，这是一个蹩脚的问题。

不过，让我们看看如果我们决定尝试解决这个问题会发生什么。

但是等等，他们还告诉您任何树的两个孩子都可以交换。这增加了这样的约束：任何与其他任何东西（包括其自身）相同的树都必须等于其镜像。其子树的子树的任何变体都被交换。

请记住，这应该是一个搜索树。因此，我们可以假设由相同算法处理的两个不同的搜索树如果相等，则必须给出相同的结果。因此，如果我们交换树的元素，那么搜索时间就会受到影响。因此，没有每个节点都到位的树彼此不相等。

将其与该等式的“可交换”属性放在一起，我们可以看到这不是一个有效的等式定义。 （如果我们尝试应用它，那么事实证明，只有特定级别的每个节点都具有相同节点的树才相等，并且仅对它们自己而言，这打破了相等运算符的自反性部分。）

Answer 2

我不认为这是一个无理的问题。一种简单的递归解决方案是

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;
}

这可能非常昂贵，例如，当我们有两棵形状相似的大树时，其中所有非叶节点都具有相同的关联值，并且其中一棵树的叶节点是叶节点的排列另一个。

为了解决这个问题，您可以首先根据需要更改 left 和 right ，以便 left <对，对于 < 的一些递归定义。这也可能很昂贵，但比检查每个排列要便宜得多，而且我认为选择 << 的定义。会有帮助的。这将允许您检查与普通定义的相等性。

http://en.wikipedia.org/wiki/Canonicalization 的概念也遵循普通的平等解决有关是否确实存在等价关系的问题。等价关系相当于划分。普通的平等显然是一种划分。如果通过比较 f(x) 和 f(y) 以及等价关系来比较 x 和 y，则您将得到 x 和 y 的划分，从而得到等价关系。

进一步思考这一点，我认为使规范化或相等测试相当有效的方法是自下而上工作，用一个标记注释每个节点，该标记的值反映与其他节点比较的结果，以便您可以比较节点，以及它们下面的子树，只是比较标记。

因此，平等的第一步是使用哈希表用标记来注释每个叶子，只有当叶子上的值相等时，这些标记才相等。然后，对于其唯一子节点是叶子的节点，使用例如哈希表来分配进一步的标记，使得仅当这些节点下方的叶子（如果有）匹配时，这些节点中的标记才相等。然后您可以再上一步，这一次您可以比较子节点处的标记，而不是向下递归树。以这种方式分配代币的成本应该与所涉及的树的大小成线性关系。在顶部，您可以通过比较根处的标记来比较树。

Answer 3

如果你用翻转不变性来实现他们对“平等”的定义，你将违反平等的定义。这个定义甚至没有意义，因为二叉搜索树不是相等的（除非每个节点都有一个指针，指向哪个子树“更大”，哪个子树“更小”）。

您有两种合理的定义选择：

1. 拓扑（与翻转无关）等价（在这种情况下，您不能将其称为“二叉搜索树”，因为它未排序）：

   tree1==tree2 表示set(tree1.children)==set(tree2.children)

2. 普通搜索树（翻转关怀）等价：

   tree1==tree2 表示 list(tree1.children)==list(tree2.children)

对于二叉树，上述定义将以任何支持 list 和 set 数据类型的语言按原样工作（但是 python 集在不可散列的数据类型上会阻塞）。尽管如此，下面是一些更冗长和丑陋的类似 C/Java 的定义：

1. 拓扑等效：

   t1==t2 表示 (t1.left==t2.left and t1.right==t2.right) 或 (t1.left==t2.right and t1.右==t2.左）

2. 排序树等价：

   t1==t2 表示(t1.left==t2.left and t1.right==t2.right)

上面的定义是递归的；也就是说，他们假设已经为子树和基本情况定义了相等性，确实如此。

---

旁注：

引用：tree1->child == tree2->child

这不是一个有效的语句，因为树节点没有单个子节点。

Answer 4

使用 @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

Answer 5

我将问题读为：给定两个二叉树，对于树中的每个深度，找出它们的子集是否相互覆盖。

这可以相对容易地编码。

Answer 6

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 语法提示：

• (1) 将元素放入数组： arr <<元素;在本例中，for_check 是数组的数组
• (2) 并行赋值：t1,t2 = [item1, item2]。与arr = [item1, item2]相同； t1 = arr[0]; t2 = arr[1]
• (3) t1_children == t2_children 假设此类对象具有 == 的相应行为。更详细的是 t1_children.map { |el| el.val } == t2_children.map { |el| el.val } - 这里 map 生成 vals 数组。