# 50221. Pascal's triangle

## I'm a slow walker, but I never walk backwards.

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 11 4 21 -1 -11 5 42 -1 -11 -1 -1

## Estimated Cyclomatic Number

6.3