欢迎访问我的Uva题解目录哦 https://blog.****.net/richenyunqi/article/details/81149109

题目描述

题意分析

给一棵二叉树，每个结点都有一个水平位置：左子结点在它左边1个单位，右子结点在右边1个单位。从左向右输出每个水平位置的所有结点的权值之和。如图6-7所示，从左到右的3个位置的权和分别为7，11，3。按照递归（先序）方式输入，用-1表示空树。

算法分析

可以利用map<int,int>来存储每个水平位置的所有结点权值之和，键表示水平位置，值表示结点权值之和。假设根结点所在水平位置为0，则根结点的左孩子节点水平位置为-1，右孩子节点水平位置为1。由于map<int,int>按键从小到大排序，则结点权值之和在map中恰好是按水平位置从左到右排放的，得到结果遍历输出即可。
本题只要求输出每个水平位置的所有结点权值之和，不需要真正建立一棵树，在读取输入数据时直接对每个水平位置的结点权值进行加和即可。具体实现可见代码。

C++代码

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int data;//数据域
    Node*left,*right;//左右孩子指针
    Node(int d,int p):data(d),left(nullptr),right(nullptr){}
};
map<int,int>ans;
//返回false代表空树，参数p代表当前结点水平位置，参数root代表当前结点是不是根结点
bool DFS(int p,bool root){
    int data;
    scanf("%d",&data);
    if(data==-1)//读取到的数据为-1
        if(root)//如果当前结点是根结点
            return false;//树为空树，返回false
        else//不是根结点
            return true;//树不是空树，返回true
    if(root)//是根结点
        ans.clear();//清空map
    ans[p]+=data;//在对应水平位置加上结点权值
    DFS(p-1,false);//递归遍历左子树
    DFS(p+1,false);//递归遍历右子树
    return true;//返回true,代表不是空树
}
int main(){
    while(true){
        for(int i=1;DFS(0,true);++i){
            printf("Case %d:\n",i);
            for(auto j=ans.begin();j!=ans.end();++j)
                printf("%s%d",j==ans.begin()?"":" ",j->second);
            printf("\n\n");
        }
        break;
    }
    return 0;
}