确定两个二叉树是否相等

Question

如果两个给定的二叉树是相等的 - 在结构和内容中,找到有效的算法是什么？

Answer 1

这是一个小问题,但我会按照以下方式调整早期解决方案......

eq(t1, t2) =
  t1.data=t2.data && eq(t1.left, t2.left) && eq(t1.right, t2.right)

原因是不匹配可能很常见,最好在提前再次检测之前检测(并停止比较).当然,我在这里假设一个短路&&运算符.

我还要指出,这正在掩盖一些问题,正确处理结构上不同的树,并结束递归.基本上,需要对t1.left等进行一些空检查.如果一棵树有一个null .left但另一棵没有,你发现了结构上的差异.如果两者都有null .left,则没有区别,但是你已经达到了一个叶子 - 不要进一步递减.只有当两个.left值都为非null时,才会递归检查子树.当然,这同样适用于.right.

您可以包含例如(t1.left == t2.left)的检查,但这只有在可以为两棵树物理共享子树(相同的数据结构节点)时才有意义.这种检查将是避免在不必要的地方进行递归的另一种方法 - 如果t1.left和t2.left是相同的物理节点,您已经知道那些整个子树是相同的.

AC实施可能是......

bool tree_compare (const node* t1, const node* t2)
{
  // Same node check - also handles both NULL case
  if (t1 == t2)  return true;

  // Gone past leaf on one side check
  if ((t1 == NULL) || (t2 == NULL))  return false;

  // Do data checks and recursion of tree
  return ((t1->data == t2->data) && tree_compare (t1->left,  t2->left )
                                 && tree_compare (t1->right, t2->right));
}

编辑回复评论......

使用它进行完整树比较的运行时间最简单地表示为O(n),其中n有点像树的大小.如果你愿意接受更复杂的界限,你可以得到一个较小的界限,如O(最小(n1,n2)),其中n1和n2是树的大小.

解释基本上是递归调用仅对左树中的每个节点进行一次(最多)一次,并且仅对右树中的每个节点进行一次(最多)一次.由于函数本身(不包括递归)最多只指定一定量的工作(没有循环),所以包括所有递归调用的工作只能与较小树的大小一样多.

您可以使用树的交叉点来进一步分析以获得更复杂但更小的边界,但是大O只给出上限 - 不一定是最低可能的上限.除非你试图用它作为一个组件构建一个更大的算法/数据结构,否则可能不值得进行这种分析,因此你知道某些属性将永远应用于那些可能允许你更紧密绑定的树.更大的算法.

形成更严格界限的一种方法是考虑两个树中节点的路径集.每个步骤是L(左子树)或R(右子树).因此,根用空路径指定.根的左孩子的右孩子是"LR".定义函数"paths(T)"(数学上 - 不是程序的一部分)来表示树中的有效路径集 - 每个节点一条路径.

所以我们可能会......

paths(t1) = { "", "L", "LR", "R", "RL" }
paths(t2) = { "", "L", "LL", "R", "RR" }

相同的路径规范适用于两个树.并且每个递归始终遵循两个树的相同左/右链接.因此递归访问这些集合的路径中的路径,并且我们可以使用此指定的最严格的边界是该交集的基数(仍然与每次递归调用的工作的常量限制).

对于上面的树结构,我们对以下路径进行递归...

paths(t1) intersection paths(t2) = { "", "L", "R" }

因此,我们在这种情况下的工作最多限制为tree_compare函数中非递归工作的最大成本的三倍.

这通常是不必要的细节量,但显然路径集的交集最多与最小原始树中的节点数一样大.无论O(n)中的n是指一个原始树中的节点数还是两个中节点的总和,这显然不小于最小值或交点.因此,O(n)并不是一个如此紧密的界限,但它仍然是一个有效的上限,即使我们有点模糊,我们正在谈论的大小.