答案是14
說明
輸入給予下列資訊：
第一行會給定一個整數n，代表節點的個數。 n 最多不超過100,000。
接下來會有 n 行，每一行代表一個節點的資訊，其內容如下：
第一個數字代表節點的ID，分別是1~n不重複(不一定照順序)。
接下來會有一個字串，可能會是SUM, MIN, MAX, VAL 四種其中之一，分別代表總和、最小值、最大值、或是Leaf node。
接下來會是一個數字，代表此節點的parent ID。
如果這個節點是Leaf node (即第二個字串是VAL)，該行最後會有一個數字代表此節點的值。
(parent 是 -1 表示該node是root)
output用%d即可。
input
13
1 SUM 2
2 MAX -1
3 SUM 2
4 MAX 3
5 VAL 1 3
6 MIN 1
7 VAL 1 2
8 VAL 3 6
9 VAL 6 4
10 VAL 6 2
11 VAL 4 5
12 VAL 4 3
13 VAL 4 8
output
14
解法：
因為不是binary tree。
所以做left child right sibling。
再做traverse即可。
太久沒寫tree，我的指標又在飄了 lol~
#include <stdio.h>
#include <string.h>
#define MAXNODE 100001
typedef struct node {
char data[4];
int value;
struct node *left;
struct node *right;
} Node;
void init(Node *nodes, int n);
void addchild(Node *node, Node *child);
int traverse(Node *node);
int sum(Node *node);
int max(Node *node);
int min(Node *node);
int main(void)
{
int n, i, p, root, index;
Node nodes[MAXNODE];
scanf("%d", &n);
init(nodes, n);
for (i = 0; i < n; i++) {
// input
scanf("%d", &index);
scanf("%s %d", nodes[index].data, &p);
if (strcmp(nodes[index].data, "VAL") == 0) {
scanf("%d", &nodes[index].value);
}
if (p == -1)
root = index;
else
addchild(&nodes[p], &nodes[index]);
}
printf("%d\n", traverse(&nodes[root]));
return 0;
}
void init(Node *nodes, int n)
{
int i;
for (i = 1; i <= n; i++) {
nodes[i].left = nodes[i].right = NULL;
}
}
void addchild(Node *node, Node *child)
{
if (node->left == NULL) {
node->left = child;
return;
}
else
node = node->left;
while (node->right != NULL)
node = node->right;
node->right = child;
}
int traverse(Node *node)
{
// no child is leaf
if (node->left == NULL) {
return node->value;
}
if (strcmp(node->data, "SUM") == 0) {
return sum(node->left);
}
else if (strcmp(node->data, "MAX") == 0) {
return max(node->left);
}
else if (strcmp(node->data, "MIN") == 0) {
return min(node->left);
}
}
int sum(Node *node)
{
int sum = traverse(node);
while (node->right != NULL) {
sum += traverse(node->right);
node = node->right;
}
return sum;
}
int max(Node *node)
{
int max = traverse(node);
int temp;
while (node->right != NULL) {
temp = traverse(node->right);
if (max < temp)
max = temp;
node = node->right;
}
return max;
}
int min(Node *node)
{
int min = traverse(node);
int temp;
while (node->right != NULL) {
temp = traverse(node->right);
if (min > temp)
min = temp;
node = node->right;
}
return min;
}
