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

雨点打透心脏的1/2处 2022-02-27 05:58 184阅读 0赞

![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;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsZXgxOTk3MjIy_size_16_color_FFFFFF_t_70]: /images/20220227/f1d04b89a0044a4ebd0c02546fbf77cc.png