The Falling Leaves UVA - 699 (二叉树列和）-蒲公英云

The Falling Leaves UVA - 699 (二叉树列和）

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsZXgxOTk3MjIy_size_16_color_FFFFFF_t_70

解题思路:

可以设定一个中间值pos,每次插入结点时往左节点为pos-1,右节点为pos+1,开一个数组累加每个pos的和,最后输出

数据的输入为先序遍历顺序,-1为空结点

if (cin.get() == ‘\n’) return; 可以检测回车换行

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
const int MAXN = 10010; //结点个数
int sbTree[MAXN];  //树
bool isroot = true;
int tempNode;
int sindex = 0;
void dfs_tTree(int spos) {
    cin >> tempNode;
    if (isroot == true && tempNode == -1) return;
    isroot = false;
    if (cin.get() == '\n') return;  //检测回车
    if (tempNode == -1) return;  //如果是-1,则直接退出
    sbTree[spos] += tempNode; //首先进行赋;
    dfs_tTree(spos - 1);
    dfs_tTree(spos + 1);
}
int main() {
    while (true) {
        isroot = true;
        memset(sbTree, 0, sizeof(sbTree));
        dfs_tTree(MAXN/2);
        if(isroot == true) break;
        //输出结果
        bool falg = true;
        printf("Case %d:\n", ++sindex);
        for (int i = 0; i < MAXN; ++i) {
            if (sbTree[i] != 0 && sbTree[i] != -1) {
                if (falg) {
                    printf("%d", sbTree[i]);
                    falg = false;
                }
                else {
                    printf(" %d", sbTree[i]);
                }
            }
        }
        cout << endl<<endl;
    }
    system("PAUSE");
    return 0;
}