做出來還是很happy。
(一次就AC超爽的)
解法很正統……
先建tree,之後才做traversal。
(1)建tree
因為()會是pair,所以先找到「(」即可丟入addtree()中,
當找到「)」後就return。
利用recursive就能建立完成。
(2)traversal
做preorder traversal,
利用stack紀錄每個node的value。
到leaf node時做sum,把sum存起來。
最後判斷input值是否與sum相同即可。
看到別人的解法是可以在建tree的同時做sum,
這樣之後就不用作traversal,會比較快。
/* ACM 112 Tree Summing * mythnc * 2011/12/18 19:06:31 * run time: 0.064 */ #include <stdio.h> #include <stdlib.h> #include <ctype.h> #define MAXCHAR 11 #define MAXN 1000 #define TRUE 1 #define FALSE 0 typedef struct node { char value[MAXCHAR]; struct node *left, *right; } Node; Node *addtree(void); void traversal(Node *, int *, int *); int contain(int, int *, int); void freet(Node *); int stack[MAXN]; int stc; int main(void) { Node *root; int n, c, count; int sumall[MAXN]; while (scanf("%d", &n) == 1) { /* find the 1st '(' */ while ((c = getchar()) != '(') ; root = addtree(); count = 0; traversal(root, sumall, &count); if (contain(n, sumall, count)) printf("yes\n"); else printf("no\n"); freet(root); } return 0; } /* addtree: add node to root */ Node *addtree(void) { Node *tmp; int c, left, vcount; tmp = (Node *)malloc(sizeof(Node)); tmp->left = tmp->right = NULL; left = FALSE; vcount = 0; while ((c = getchar()) != ')') /* left node */ if (c == '(' && !left) { tmp->left = addtree(); left = TRUE; } /* right node */ else if (c == '(' && left) tmp->right = addtree(); /* integer */ else if (isdigit(c) || c == '-') { tmp->value[vcount] = c; tmp->value[++vcount] = '\0'; } if (vcount == 0) { free(tmp); return NULL; } return tmp; } /* traversal: traversal the tree */ void traversal(Node *pt, int *sumall, int *count) { int i, sum; /* empty tree */ if (pt == NULL) return; /* leaf node: left and right are NULL */ if (pt->left == pt->right) { for (sum = i = 0; i < stc; i++) sum += stack[i]; sumall[(*count)++] = sum + atoi(pt->value); return; } /* push */ stack[stc++] = atoi(pt->value); traversal(pt->left, sumall, count); traversal(pt->right, sumall, count); /* pop */ stc--; } /* contain: if n contain in sumall, * return TRUE, else return FALSE */ int contain(int n, int *sumall, int count) { int i; /* negative */ if (count == 0 && n < 0) return TRUE; for (i = 0; i < count; i++) if (sumall[i] == n) return TRUE; return FALSE; } /* freet: free all node */ void freet(Node *pt) { if (pt == NULL) return; freet(pt->left); freet(pt->right); free(pt); }
沒有留言:
張貼留言