Description

Given a binary tree, print the sum of nodes in the tree.

This problem will give you the inorder and preorder sequences to build a tree, and you have to write a function to count the sum of nodes in the tree. To solve this problem, you can write a recursive function to traverse the tree and sum up the data of nodes.

You will be provided with main.c and function.h. main.c contains the implementation of functions which build a tree by the inorder and preorder, and function.h contains the definition of tree node. You only need to implement Sum(Node *root) and print the sum in function.c.

For OJ submission:

        Step 1. Submit only your function.c into the submission block.(Please choose C compiler)

        Step 2. Check the results and debug your program if necessary.

 

main.c

#include <stdio.h> #include <stdlib.h> #include "function.h" int main(void) { int *in, *pre, n, i; scanf("%d", &n);// get the size of tree in = (int *) malloc(n * sizeof(int));//allocate space for inorder pre = (int *) malloc(n * sizeof(int));// allocate space for preorder for(i=0; i<n; i++)// read in inorder scanf("%d", &in[i]); for(i=0; i<n; i++)// read in pre-order scanf("%d", &pre[i]); Node *root = constructTree(in, pre, 0, n-1);// construct trr printf("%d", Sum(root)); destroyTree(root);// clean up free(in); free(pre); return 0; } int idxSearch(int arr[], int strt, int end, int value) { int i; for (i = strt; i <= end; i++) { if (arr[i] == value) return i; } } Node* newNode(int val) { Node *node = (Node *)malloc(sizeof(Node));; node->data = val; node->left = node->right = NULL; return (node); } Node* constructTree(int inorder[], int preorder[], int inorder_start, int inorder_end) { static int preorder_idx = 0; if(inorder_start > inorder_end) return NULL; Node *tree_node = newNode(preorder[preorder_idx++]); if(inorder_start == inorder_end) return tree_node; int inorder_idx = idxSearch(inorder, inorder_start, inorder_end, tree_node->data); tree_node->left = constructTree(inorder, preorder, inorder_start, inorder_idx-1); tree_node->right = constructTree(inorder, preorder, inorder_idx+1, inorder_end); return tree_node; } void destroyTree(Node *root) { if(root != NULL) { destroyTree(root->left); destroyTree(root->right); free(root); } }

function.h

#include <stdlib.h> typedef struct treeNode { int data; struct treeNode *left; struct treeNode *right; } Node; int idxSearch(int arr[], int strt, int end, int value); Node* newNode(int val); Node* constructTree(int inorder[], int preorder[], int inorder_start, int inorder_end); void destroyTree(Node *root); int Sum(Node *root);

Input

The input contains three lines. The first line is the number of nodes in the tree. The second line is the inorder and the third line is the preorder of the tree.

Output

The output is the sum of nodes in the tree.

Sample Input  Download

Sample Output  Download

Partial Judge Code

10962.c

Partial Judge Header

10962.h

Tags

Discuss