这是工作面试问题的一部分，在第二部分变得更难了。
给定两棵 2-3 棵树 T1 和 T2 使得对于h已知的每棵树（h 表示高度）和m，M对于每棵树也是已知的（m 表示最小值，M 表示最大值），再加上每个节点T1< 中的每个节点T2。我被要求找到一种算法将它们加入一棵树O(|h1-h2|+1)
这个很简单，我必须指出，这个算法可能会导致一棵树的 h 比前两个大。
现在，我得到了k2-3 棵树 (T1,T2,T3...Tk)，它们的条件完全相同，h_1<=h_2<=...<=h_k而且知道没有三棵树的高度相同，可以将它们加入O(h_k-h_1+k)。
起初我考虑使用之前的算法将前两个连接在一起，然后将第三个连接到结果等等，但我觉得这里出了点问题，因为我没有利用“没有三棵树共享一样高”。
我在这里缺少什么？
您的解决方案是正确的，但如果您有超过 2 棵相同高度的树，则不会。例如，如果您有k相同高度的树，那么前两个确实会及时合并O(h_1 - h_1) = O(1)，但结果高度可能变为h_1 + 1. 虽然它可能只是，也可能不是这样，但让我表明一切都可能出错。
我们可以在高度树内拥有的最大键数n是3^(n+1)-1. 那是因为每个顶点最多有3个子树，因此第i层有3^i顶点，添加n层会产生(3^(n + 1) - 1)/2 顶点。因为在这种情况下每个顶点都有 2 个键，所以键的总数是 3^(n + 1) - 1。
因此，如果我们合并 4 棵这样的最大树，我们肯定会得到一棵高度增加 2 的树，16 棵合并的树得到高度增加 3，以此类推。因此，虽然前 3 次合并是在恒定时间内完成的，但接下来的 12 次合并慢了两倍，接下来的 48 次合并慢了 3 倍，依此类推。您Ω(i)将从1到Ω(3^(i+1) - 3^i).ilog(k)
因为Ω(3^log(k)) = Ω(k)这个和是肯定的Ω(k log k)，所以对于给定的渐近界是不合适的。
当没有 3 棵树共享相同的高度时，不会发生此问题，因为每当您合并两棵树时，结果高度为max(h_i, h_(i+1)) + 1 = h_(i+1) + 1, 和h_(i+3) >= h_(i+1) + 1，因此合并部分的高度永远不会比下一棵树高一倍，这就是 +k 部分的来源在渐近界。