Seesaw Chandelier Tree

[littlehug]

Write a function to construct a seesaw chandelier tree.

Task Description

A seesaw chandelier is a hierarchy of seesaws in which every seesaw is balanced. A seesaw chandelier can be recursively defined as follow. A balancing point is defined as in the previous tasks.

• If there is a balancing point, then the balancing point links to another seesaw chandelier with a "left" pointer, and links to the other seesaw chandelier with a "right" pointer.
• If there is no balancing point, then a seesaw chandelier has a sequence of nodes linked by the "left" pointer as a linked list.

We want to build a seesaw chandelier tree from a sequence of n non-negative integers, indexed from 0 to n-1. For the first level, we consider the whole sequence as a seesaw and find the balancing point at index i between 0 to n-1, as we did in the previous tasks. Now the root of the tree is the balancing point at index i and two partitions -- one on the left tree and one on the right tree. The one on the left has index from 0 to i-1, and the one on the right has index from i+1 to n-1. Now we consider these two partitions as two independent seesaw hierarchies and find the balancing points for them. We can recursively do this until the length is less than 3, or we cannot find a balancing point for a partition. In both cases we stop the recursion and use left pointer to link all the nodes in the partition from right to left. Please refer to the second condition in the previous recursive definition.

For example, we now want to build a seesaw chandelier with a sequence of 8 non-negative integers, (2, 5, 2, 0, 7, 1, 7, 4). At the first level, we can find the balancing point at 7 (with index 4), because 2 * 4 + 5 * 3 + 2 * 2 + 0 * 1 = 1 * 1 + 7 * 2 + 4 * 3. Then we partition the sequence into two sequences, (2, 5, 2, 0) and (1, 7, 4). Then we recursively find the balancing points for them. We can find 5 (index 1) for the partition on the left, because 2 * 1 = 2 * 1 + 0 * 2, but no balancing point on the right. After that the recursion stops and we link the nodes in each partition from right to left since we cannot find a balancing point for the new partitions or the length is less than 3.

figure

Note that if the seesaw has balancing point, then there is only one balancing point since there is only one center of mass for every seesaw. In addition, the torque needs to be stored in a “long long int” to prevent integer overflow. All pointers must be set to NULL if they are not used to link the seesaws together.

Please construct the seesaw chandelier tree in the function, “Node *ConstructTree( … )”, then return the pointer of the root. The main program and the prototype of function “ConstructTree” are as followed:

/*construct.h*/
#ifndef CONSTRUCT
#define CONSTRUCT
typedef struct Node{
    int value;
    struct Node *left, *right;
} Node;

Node *ConstructTree(int T[], int N);
#endif

/*main.c*/
#include <stdio.h>
#include "construct.h"

#define MAXN 16384

int T[MAXN];

void PrintTree( Node *root ){
    if (root == NULL)
        return;

    printf("%d\n", root->value);
    PrintTree(root->left);
    PrintTree(root->right);
    return;
}

int main(){
    int N;
    scanf("%d", &N);
    for (int i=0; i<N; i++)
        scanf("%d", &T[i]);

    Node *tree = ConstructTree( T, N );

    PrintTree( tree );
    return 0;
}

Subtasks

• 10 points: It is guaranteed you will find a balancing point at the top level, and none at the second level.
• 20 points: It is guaranteed you will find a balancing point at the top level and the second level, but none at the third level.
• 70 points: It is guaranteed you will find a balancing point at the top, but nothing is guaranteed at other levels.

Input Format

The input contains only one test case. The first line contains one integers n, representing the number of sequence. The second line contains n integers, w1, w2, … , wn, representing the weights of index.
0 < n < 16384

Output Format

Print all the values of nodes in the tree by pre-ordering, and each node in a line.

Sample Input 1

4
2 1 5 5

Sample Output 1

5
1
2
5

Sample Input 2

9
2 5 2 0 7 1 1 4 3

Sample Output 2

7
5
2
0
2
4
1
1
3

Sample Input 3

8
2 5 2 0 7 1 7 4

Sample Output 3

7
5
2
0
2
4
7
1