如何合并满足堆序的两棵树？能否在O(m+n+1)时间复杂度内完成？

问题描述 #

我想合并两棵满足堆序的树，请问是否可以在O(m+n+1)的时间复杂度内完成该操作？其中m、n分别为输入两棵树的高度。
输入输出示例：

Input:
   10              8
     \
      9 
Output: (可输出任意一个符合要求的结果)
   10               10             10          10
     \             /  \           /  \        /  
      9           9    8         8    9      9
     /                                      /
    8                                      8

结论 #

完全可以，实际所需时间甚至远低于这个复杂度上限。

具体说明 #

以示例中的大顶堆场景为例（堆序要求为任意父节点值大于等于子节点值，小顶堆场景只需要把比较逻辑反过来即可）：

• 首先比较两棵树的根节点值，取数值更大的根作为合并后新树的根
• 另一棵树可以整体直接挂载到新根的任意空子节点位置，也可以挂载到新树任意符合堆序要求的节点的空子节点上，比如示例里把值为8的树挂载到值为9的节点的左子节点，8<9、9<10，完全符合堆序要求
  整个操作只需要一次根节点比较和一次节点挂载，实际时间复杂度只有O(1)，远低于O(m+n+1)的要求，完全可以在你给出的时间范围内完成。

内容的提问来源于stack exchange，提问作者Jason