uva 699 (이 진 트 리)

문제 풀이: 이 문 제 는 나 무 를 만 들 때 위치 에 있 는 매개 변 수 를 전달 하여 각 잎 의 합 을 업데이트 해 야 한다. 문제 에 서 는 중첩 수가 80 을 넘 지 않 는 다 는 설명 이 있 으 면 위치 40 부터 배열 에 저장 해 야 한다.

#include 
#include 
const int N = 85;
struct Node {
    int val;
    Node* left;
    Node* right;
    Node () {
        val = -1;
        left = right = NULL;
    }
};
int ans1[N], ans2[N];

Node* build(int pos, int a) {
    int n;
    char c;
    Node* node = new Node;
    scanf("%d%c", &n, &c);
    if(n != -1) {
        node -> val = n;
        ans1[pos] += n;
        node -> left = build(pos - 1, 1);
        node -> right = build(pos + 1, 2);
    }
    else {
        if (a == 1)
            pos += 1;
        else if (a == 2)
            pos -= 1;
        return NULL;
    }
    return node;
}

void Delete(Node* node) {
    if (node == NULL)
        return;
    if (node -> left != NULL)
        Delete(node -> left);
    if (node -> right != NULL)
        Delete(node -> right);
    delete node;
}

int main() {
    int cases = 1;
    char c;
    Node* root;
    while (1) {
        memset(ans1, 0, sizeof(ans1));
        root = build(40, 0);
        if (root == NULL)
            break;
        else {
            printf("Case %d:
", cases++);
            int k = 0;
            for (int i = 0; i < N; i++)
                if (ans1[i] > 0) {
                    ans2[k++] = ans1[i];
            }
            for (int i = 0; i < k - 1; i++)
                printf("%d ", ans2[i]);
            printf("%d

", ans2[k - 1]);
            Delete(root);
        }
    }
    return 0;
}