UVA699-例题6-10 下落的树叶(The Falling Leaves,UVa 699)

72 阅读 0 评论 48 点赞

我是靠谱客的博主顺利白昼，最近开发中收集的这篇文章主要介绍UVA699-例题6-10 下落的树叶(The Falling Leaves,UVa 699)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

原题链接： UVa-699

题目大意：

题意为给一棵二叉树，求从左向右输出每个水平位置的所有结点的权值之和。输入按照递归（先序）方式，-1表示空树。

解题思路：

本题是《算法竞赛入门经典》第六章例题，本题的主要解题思路就是使用递归根据输入直接计算每个水平位置的的权值之和。

一开始看完题之后也想着用数组来存储每一列的权值之和。但是由于下标的问题感觉处理起来过于麻烦。就有想想有没有其他的办法，由于上一章学的STL，就想着能不能用容器来存储。后来决定用map来进行存储。（不过我很怀疑是不是多次一举，因为需要的数组应该也不会很大。）递归部分就是根据深度优先算法（先序）来构造二叉树，同时累加每一列的权值和。

代码：

#include<iostream>
#include<map>
#include<cstring>
#include <sstream>
#include<string>

using namespace std;

void cal(int p);

map<int, int> sum;
stringstream ss;

int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	string s;
	int kase = 0;
	while (getline(cin, s) && s != "-1")  
	{
		ss.str(s);		//将s放入ss，用于转换 
		cal(0);
		cout << "Case "<< ++kase <<":n";
		int i = 0;
		for (map<int,int>::iterator it = sum.begin() ; it != sum.end() ; it++)//遍历结果map 
		{
			cout << it->second;
			if(i<sum.size()-1)	//用于控制输出空格 
				cout << " ";
			i++;
		}
		cout << endl<<endl;
		sum.clear();//清理 
		ss.clear();
	}
	return 0;
}

//递归构造二叉树的过程中计算每个结点所在的列的最新的权值和 
void cal(int p)
{
	int wgt;
	ss >> wgt;
	if (wgt == -1)
		return;
	if (!sum.count(p)) sum[p] = 0;
	sum[p] += wgt;
	cal(p - 1);
	cal(p + 1);
}