Description
This is a partial judge problem. ༼≖ɷ≖༽
typedef struct _Node {
struct _Node *left, *right;
int id;
} Node;
First you have a structure of Node, id represents the index, left and right represents the left node and right node.
Node* buildBinaryTree(int, int*, int*);
void Traversal(Node*, int*);
void freeBinaryTree(Node*);
You're asked to implement the above three functions.
First, build a binary tree according to the input, next calculate the size of every subtree in one tree traversal. Lastly, free the memory if you ever malloc any.
There's a comment in the header file, maybe it's useful. :P
If you think the above description is not clear, you should trace the sorce code for detailed.
You're highly recommended to create an additional file function.c and compile it with the main source code instead of putting everything in one file.
Note:
This is a binary patrick star.
The following graph is the tree of the first sample input.
Input
The input file contains several testcases (less than 10).
For each testcase, first line contains a single integer N, (1 <= N <= 1000000) represent the number of nodes. The index of nodes is 0 ~ n - 1.
The following N lines each contains two integers represent the left child and right child of the node staring from 0 to n - 1.
If either left child or right child doesn't exist, the value would be -1.
Guarantee the input forms a binary tree and the node 0 is the root.
Output
For each testcase output the subtree size of every node starting from 0 to n - 1 seperated by space.