例如:
两棵树:
8 9 5 7 4 20 30
变成一棵树?
没有更多细节/约束,最简单的解决方案是获取任一棵树的叶子节点,将其删除,并将其用作新创建的三棵树的根。
在您的示例中:
30 8 9 5 7 4 20
之所以可行,是因为您的树木似乎没有遵循任何特定的顺序,似乎没有平衡,也没有任何其他约束。
由于任何叶节点都会这样做,因此在最坏的情况下,这是一个 O ( n )操作(以任何顺序遍历一棵树,直到遇到第一个叶,将其删除,然后将子链接添加到两棵树的根中)。