uva 699 The Falling Leaves

点击打开链接

题目意思：给定一串数字，第一个是根节点的值，接下来如果遇到-1 则该点为空，不是-1则创建节点，求最后从左往右每一条竖线的和 分别输出。

解题思路：1 建树 2 前序遍历求和 3 输出 （这里刚误删了，晚了得睡觉了，有时间更新）

注意事项：我们可以采用，把-1 这个节点的val 赋值成很小的数，然后不让它为空，后面计算时候算到这个点直接跳过

代码：

#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <stack>
#include <list>
#include <algorithm>
using namespace std;
const int MAXN = 1000010;
const int MIN  = -999999999;

int num[MAXN];
int ans[1000];
int mark;//用来标记是否创建过

//二叉树的结构体
struct Btree{
    int val;
    struct Btree *lchild;
    struct Btree *rchild;
    struct Btree *father;
};
Btree *root;//根节点
Btree *cur;//当前节点
Btree *temp;//临时用的

//根节点的初始化
void init(Btree *u , int n){
    u -> father = NULL;
    u -> lchild = NULL;
    u -> rchild = NULL;
    u -> val = n;
}
//增加新的节点
void creatnode(int tempval){
    temp = new Btree;//分配空间
    mark++;
    if(tempval == -1){//如果为-1
        init(temp , MIN);
        if(cur -> lchild == NULL){ //左子树为空
            cur -> lchild  = temp;
            cur -> lchild != NULL;
        }
        else{
            cur -> rchild   = temp;
            cur -> rchild  != NULL;
            while(cur->rchild != NULL && cur != root)//退回去，注意要找到它的右子树为空
                cur = cur -> father;
        }
    }
    else{//不是-1
        init(temp , tempval);//初始化
        if(cur -> lchild == NULL) {//左子树为空
            cur -> lchild = temp;
            temp = cur;
            cur  = cur -> lchild;
        }
        else{
            cur -> rchild = temp;
            temp = cur;
            cur  = cur -> rchild;
        }
        cur -> father = temp;//当前节点重新赋值
    }
}

//前序遍历求和
void preorder(Btree *u , int p){
    if(u!=NULL){
        if(u -> val != MIN)//只要不是MIN就相加
           ans[p] += u->val;
        preorder(u->lchild , p-1);//这里不要写p--;
        preorder(u->rchild , p+1);//这里不要写p++;
    }
}

//输出函数
void output(){
    int i , j;
    for(i = 0 ;i < 1000 ; i++){
        if(ans[i] != 0)
            cout<<ans[i];
        if(ans[i+1] != 0)
            cout<<" ";
    }
    cout<<endl<<endl;
}

//主函数
int main(){
    int i ,j , k = 1 ,rootnum , nodenum;
    while(cin>>rootnum && rootnum != -1){
        root = new Btree;//产生根节点
        init(root , rootnum);//初始化
        cur = root;//当前节点为根节点
        mark = 0;
        while(1){
            scanf("%d" , &nodenum);//输入节点值
            creatnode(nodenum);
            if(nodenum == -1 && cur == root && mark != 0 && cur->lchild != NULL && cur->rchild != NULL)//停止输入情况
                break;
        }
        memset(ans , 0 , sizeof(ans));
        preorder(root , 500);//前序遍历求和
        printf("Case %d:" , k);
        output();
        k++;
    }
}