组合两个二叉树的算法？

Question

例如:

两棵树:

       8                   9
   5        7          4       20
                    30

成为一棵树？

Answer 1

如果没有更多细节/约束,最简单的解决方案是获取任一树的叶节点,将其删除,并将其用作新创建的树的根.

在你的例子中:

             30
    8                   9
5        7          4       20

这是有效的,因为您的树似乎不遵循任何特定顺序,看起来不平衡,也没有任何其他约束.

由于任何叶节点都会这样做,所以在最坏的情况下这是一个O(n)操作(以任何顺序遍历其中一个树,直到我们遇到第一片叶子,将其删除,添加到两个树根的子链接).