50221. Pascal's triangle

Task Description

Write a program to build Pascal's triangle of height $H$ with an array $A$ of $H (H + 1) /2 $ nodes. The structure of Pascal's triangle is as follows. Each node has a left and a right pointer. The nodes' numbers indicate the node's index in the array. If a pointer does not point to a node in the triangle, it should be NULL. Please refer to the following figure for an illustration.

fig1

Now we need to fill the values into Pascal's triangle. If a node has two parents, then its value is the sum of the values of its parent. If a node does not have two parents, its value is 1. Please refer to the following figure.

fig2

The definition of a node and the prototype of the function build_Pascal are in Pascal.h.

typedef struct node {
    int value;
    struct node *left;
    struct node *right;
} Node;
 
void build_Pascal(Node* node_array, int height);

You can use the following main.c to test your function.

#include "stdio.h"
#include "stdlib.h"
#include "Pascal.h"
 
int main(){
    int height;
    scanf("%d", &height);
    int node_num = height * (height+1) / 2;
    Node* node_array = (Node*)calloc(node_num, sizeof(Node));
    build_Pascal(node_array, height);
 
    for (int i = 0; i < node_num; i++){
        int value = node_array[i].value;
        int left = (node_array[i].left == NULL)? -1 : (node_array[i].left - node_array);
        int right = (node_array[i].right == NULL)? -1 : (node_array[i].right - node_array);
        printf("%d %d %d\n", value, left, right);
    }
    free(node_array);
    node_array = NULL;
    return 0;
}

Limits

$H$ is no more than $25$.

Input Format

The input has a positive integer, the tree height $H$.

Output Format

There are several lines in the output. Each line has the value, the left child index, and the right child index of a node. We will check if the result of your function is correct.

Sample Input 1

3

Sample Output 1

1 3 1
1 4 2
1 -1 -1
1 5 4
2 -1 -1
1 -1 -1

Estimated Cyclomatic Number

6.3