2个二叉树是否相等

Question

可能重复:
确定两个二叉树是否相等

昨天接受采访,一个问题让我,这里是:

描述

有2 binary trees,检查他们是否平等.

当且仅当tree1->child == tree2->child一棵树左右时,它们是相等的children can be swapped with each other.

例如:

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

这可能非常昂贵,例如在我们具有两个相似形状的大树的情况下,其中所有非叶节点具有相同的关联值并且一个的叶节点是另一个的叶节点的排列.

为了超越这个,你可以首先根据需要左右改变,以便左<右,对于<的一些递归定义.这也可能是昂贵的,但比检查每个排列要少得多,我认为选择<的定义会有所帮助.这将允许您检查与普通定义的相等性.

这个http://en.wikipedia.org/wiki/Canonicalization概念后面的普通平等也解决了你是否确实拥有等价关系的问题.等价关系等同于分区.普通的平等显然是一个分区.如果通过比较f(x)和f(y)后跟等价关系比较x和y,则得到x和y的分区,因此是等价关系.

考虑到这一点,我认为使规范化或相等测试合理有效的方法是从下到上,用一个标记来注释每个节点,该标记的值反映了与其他节点的比较结果,这样你就可以比较节点,以及它们下面的子树,只是比较令牌.

因此,相等的第一步是例如使用哈希表来使用令牌来注释每个叶子,这些令牌仅在叶子上的值相等时才相等.然后,对于其唯一子节点为叶子的节点,使用例如散列表来分配更多令牌,使得这些节点中的令牌仅在这些节点下方的叶子(如果有的话)匹配时相等.然后你可以再向上一步,这次你可以在子节点上比较令牌而不是在那里递归树.以这种方式分配令牌的成本应该与所涉及的树的大小成线性关系.在顶部,您可以通过比较根的标记来比较树.