确定两个二叉树是否相等

这是一个小问题，但我会按照以下方式采用较早的解决方案…

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

原因是不匹配很可能很常见，因此最好尽早发现（并停止比较），然后再重复进行。当然，我在这里假设短路&&运算符。

我还将指出，这掩盖了正确处理结构上不同的树并结束递归的一些问题。基本上，需要对t1.left等进行一些null检查。如果一棵树具有null
.left而另一棵树没有，则您发现了结构上的差异。如果两个都为null .left，则没有任何区别，但是您已经了解到详情-
请勿进一步递归。仅当两个.left值都不为空时，才递归检查子树。当然，.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（minimum（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）并不是一个严格的界限，但是它仍然是一个有效的上限，即使我们有点不确定我们在说什么尺寸。