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 height of every subtree in one tree traversal. Lastly, free the memory if you ever malloc any.
The height of a node is the number of nodes on the longest simple path from the node to a leaf.
If you think the above description is not clear, you should trace the source 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 2.
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 height of every subtree starting from 0 to n - 1 seperated by space.