python - 自下而上构建二叉树

Question

考虑下面的程序，它通过将节点分成两半来从上到下构建一个二叉树:

def split(n):
    if n == 1:
        return n
    m = n//2
    return [split(n-m)] + [split(m)]

例如:

for i in range(1, 10):
    print(i, split(i))

打印:

1 1
2 [1, 1]
3 [[1, 1], 1]
4 [[1, 1], [1, 1]]
5 [[[1, 1], 1], [1, 1]]
6 [[[1, 1], 1], [[1, 1], 1]]
7 [[[1, 1], [1, 1]], [[1, 1], 1]]
8 [[[1, 1], [1, 1]], [[1, 1], [1, 1]]]
9 [[[[1, 1], 1], [1, 1]], [[1, 1], [1, 1]]]

是否可以自下而上构建完全相同的树？也就是说，给定 1 的数量，递归合并两个相邻节点，直到没有更多要合并的节点为止？

如果不是，是否可以从下往上构建高度完全相同的类似树？

为了说明这个过程，以6为例:

1, 1, 1, 1, 1, 1
[1, 1], 1, 1, 1, 1
[1, 1], 1, [1, 1], 1
[[1, 1], 1], [1, 1], 1
[[1, 1], 1], [[1, 1], 1]
[[[1, 1], 1], [[1, 1], 1]]

我怎么知道什么时候“跳过”一个节点以便稍后合并它？

PS:示例是用 Python 编写的，但语言无关紧要。

Answer 1

Let n be the initial size of the array 
for(int i=0;i<log2(n);i++)
{
    Let the current size of the array be m
    for(int j=0;j<m/2;j++)
        merge two adjacent elements of the array to form a new element
    // After this some elements from first half would be single

    for(int j=m/2;j<m;j++)
        merge two adjacent elements of the array to form a new element.  
    // After this some elements from second half would be single

    // The new updated array will now have ceil(n/2) elements
}