The Falling Leaves

标签: 二叉树

The Falling Leaves

Each year, fall in the North Central region is accompanied by the brilliant colors of the leaves on the
trees, followed quickly by the falling leaves accumulating under the trees. If the same thing happened
to binary trees, how large would the piles of leaves become?
We assume each node in a binary tree ”drops” a number of leaves equal to the integer value stored
in that node. We also assume that these leaves drop vertically to the ground (thankfully, there’s no
wind to blow them around). Finally, we assume that the nodes are positioned horizontally in such a
manner that the left and right children of a node are exactly one unit to the left and one unit to the right,respectively, of their parent. Consider the following tree on the right: The nodes containing 5 and 6 have the same horizontal position (with different vertical positions, of course). The node containing 7 is one unit to the left of those containing 5 and 6, and the node containing 3 is one unit to their right. When the ”leaves” drop from these nodes, three piles are created: the leftmost one contains 7 leaves (from the leftmost node), the next contains 11 (from the nodes containing 5 and 6), and the rightmost pile contains 3. (While it is true that only leaf nodes in a tree would logically have leaves, we ignore that in this problem.)
在这里插入图片描述
Input
The input contains multiple test cases, each describing a single tree. A tree is specified by giving the
value in the root node, followed by the description of the left subtree, and then the description of the
right subtree. If a subtree is empty, the value ‘-1’ is supplied. Thus the tree shown above is specified
as ‘5 7 -1 6 -1 -1 3 -1 -1’. Each actual tree node contains a positive, non-zero value. The last test
case is followed by a single ‘-1’ (which would otherwise represent an empty tree).
Output
For each test case, display the case number (they are numbered sequentially, starting with 1) on a line
by itself. On the next line display the number of “leaves” in each pile, from left to right, with a single
space separating each value. This display must start in column 1, and will not exceed the width of an
80-character line. Follow the output for each case by a blank line. This format is illustrated in the
examples below.
Sample Input
5 7 -1 6 -1 -1 3 -1 -1
8 2 9 -1 -1 6 5 -1 -1 12 -1
-1 3 7 -1 -1 -1
-1
Sample Output
Case 1:
7 11 3
Case 2:
9 7 21 15

题解

给你一个先序二叉树,其中左子结点在父节点左一个单位,右节点在父节点右一个单位;让从左到右输出每个水平位置的权值和
因为每个节点的root不同,所以考虑到从MAXN/2开始,-1,+1进行建树不就可以了么,每次如果不等于-1,就加上权值,然后找到左边最小的root,右边最大的root输出答案即可;

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
using namespace std;
#define SI(x) scanf("%d",&x)
#define mem(x,y) memset(x,y,sizeof(x))
#define PI(x) printf("%d",x)
#define P_ printf(" ")
const int INF=0x3f3f3f3f;
typedef long long LL;
const int MAXN=100010;
int tree[MAXN];
int flot,cnt;
int l,r,p;
void solve(int root)
{
    int x;
    scanf("%d",&x);
    if(!cnt&&x==-1)
    {
        flot=0;
        return;
    }
    cnt=1;
    if(x!=-1)
    {
        l=min(l,root);
        r=max(r,root);
        tree[root]+=x;
        solve(root-1);
        solve(root+1);
    }

}
int main()
{
    int kase=0;
    while(true)
    {
        flot=1;
        memset(tree,0,sizeof(tree));
        l=r=MAXN/2;
        cnt=0;
        solve(MAXN/2);
        if(!flot)break;
        printf("Case %d:\n",++kase);
        for(int i=l; i<=r; i++)
        {
            if(i!=l)P_;
            printf("%d",tree[i]);
        }
        puts("\n");
    }
    return 0;
}
版权声明:本文为rg_lzm原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/rg_lzm/article/details/99216125

智能推荐

javaScript第一天(1)

01-JavaScript基础 核心知识点 javaScript书写位置 javaScript变量 javaScript数据类型 javaScript数据类型转换 javaScript运算符 今日学习目标 能够定义一个变量并完成变量的赋值 能够说出每一种具体的数据类型 能够数据类型之间的相互转化 能够掌握各种运算符的作用 序言 JavaScript发展历史(js) JavaScript是什么? J...

VS2015错误—严重性代码说明项目文件行 禁止显示状态错误 C4996 fopen(‘fscanf‘、strcmp):This function or variable may be unsafe.

在运行时碰到下列错误: 看错误输出,需要将fopen改为fopen_s; 1.最普通的解决方法,就是使用fopen_s替代, fopen_s()函数的用法:fopen_s(_Outptr_result_maybenull_ FILE ** _File, _In_z_ const char * _Filename, _In_z_ const char * _Mode); fopen()函数的用法:f...

Vuejs——前端学习日记(二)

Vuejs——前端学习日记(二) Vue列表显示 新的指令和属性 后续 通过之前对Vuejs进行简单项目的学习,让我对Vuejs有了初步的认识,接下来是进一步的了解。 Vue列表显示 与之前看到的声明的简单变量message,name相比,数据列表是一个更加复杂的数据,所以在显示方面也会有所不同。在HTML代码中,我们会用v-for指令来显示列表。 如果用之前那样的方法来显...

设计模式之适配器模式

一、适配器模式的背景 在现实生活中,经常出现两个对象因接口不兼容而不能在一起工作的实例,这时需要第三者进行适配。例如,讲中文的人同讲英文的人对话时需要一个翻译,用直流电的笔记本电脑接交流电源时需要一个电源适配器,用计算机访问照相机的 SD 内存卡时需要一个读卡器等。 在软件设计中也可能出现:需要开发的具有某种业务功能的组件在现有的组件库中已经存在,但它们与当前系统的接口规范不兼容,如果重新开发这些...

Spring 4.x遇到的连接数据库拒绝访问

使用了Spring JdbcTemplate连接数据库, 提示 ‘Access denied for user ‘lil’@’192.168.3.104’ (using password: YES)’ , 问题记录与解决 使用了两种方法连接数据库 使用Java读取properties配置文件读取数据库配置(没有使用spring...

猜你喜欢

Day80.html的基本内容 -HTML和CSS

Html和CSS Javase → C/S模式 → Client / Server Javaweb→B/S模式 → Browser / Server 1. 前端BS软件结构 2. 前端的开发流程 3. 网页的组成部分 页面组成: 内容(结构)、表现、行为。 4. HTML简介 5… 创建HTML文件 创建一个web工程(静态的web工程) 在工...

排序算法

(1)冒泡排序 (2)快速排序参考博客(快排原理) 参考博客(形象化过程) 快排原理: 在要排的数(比如数组A)中选择一个中心值key(比如A[0]),通过一趟排序将数组A分成两部分,其中以key为中心,key右边都比key大,key左边的都key小,然后对这两部分分别重复这个过程,直到整个有序。 整个快排的过程就简化为了一趟排序的过程,然后递归调用就行了。 一趟排序的方法: 1,定义i=0,j=...

如何在Windows中获取Mac地址?

Mac Address is a network address used to layer 2 network traffic. The communication is done between network nodes with the mac address. It is important part of computer networking. In this tutorial, w...

使用stm32cubemx快速生成fatfs例程

使用stm32cubemx快速生成fatfs例程 前言 1. cubemx生成过程 1.1 sdio相关配置 1.2 系统时钟树配置 1.3 fatfs配置 1.4 修改工程的栈空间 2. 修改工程代码 2.1 fatfs sd卡读写文件的流程 2.2 具体代码的实现 3.实验现象 前言 本文将介绍如何使用stm32cubemx快速生成一个stm32 sdio 接口的fatfs例程,并实现对sd卡...

史上最简单maven配置与使用

什么是maven maven是用来帮助开发者管理项目所依赖的jar包的一款工具,创建maven工程使得开发不必再自己下载jar包,放入项目文件作为依赖,开发者只需在pom.xml文件里加入依赖的坐标即刻 什么是坐标 关于scope 配置 1、官网下载 2、环境配置 此电脑->属性->高级系统设置->环境变量 新建系统变量,变量名maven_home,变量值maven安装目录 系统...