1501 二叉树最大宽度和高度
给出一个二叉树,输出它的最大宽度和高度。
第一行一个整数n。
下面n行每行有两个数,对于第i行的两个数,代表编号为i的节点所连接的两个左右儿子的编号。如果没有某个儿子为空,则为0。
输出共一行,输出二叉树的最大宽度和高度,用一个空格隔开。
5
2 3
4 5
0 0
0 0
0 0
2 3
n<16
默认第一个是根节点
以输入的次序为编号
2-N+1行指的是这个节点的左孩子和右孩子
注意:第二题有极端数据!
1
0 0
这题你们别想投机取巧了,给我老老实实搜索!
点此展开
打递归就好。。
#include <iostream>
#include <cstring>
#include <cstdio> using namespace std; bool flag;
int kd,gd,n,i,j,lc[],rc[],fa[];
int xz(int b)
{
if (b)
{
xz(lc[b]);
gd++;
}
}
void xy(int a)
{
if (a)
{
xy(rc[a]);
kd++;
}
}
int getf(int c)
{
if (c != fa[c] && fa[c] != ) return getf(fa[c]);
else return c;
}
int main()
{
int a,b;
cin >> n;
for (i = ; i <= n; ++i) fa[i]=i;
for (i = ; i <= n; ++i)
{
cin >> a >> b;
if (a != ) lc[i]=a;
if (b != ) rc[i]=b;
if (a == && b != ) flag=;
fa[a] = getf(i);fa[b] = getf(i);
}
int maxn=;
for (i = ; i <= n; ++i)
{
int h = ;
for(j = ; j <= n; ++j)
{
if (fa[j] == i)
h++;
}
maxn = max(maxn,h);
}
xz();
xy();
if(flag)
cout<<kd<<" "<<max(maxn,gd);
else cout<<kd<<" "<<gd;
}
点击展开
Codevs 1051 二叉树最大宽度和高度的更多相关文章
-
codevs——1501 二叉树最大宽度和高度
1501 二叉树最大宽度和高度 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 题解 题目描述 Description 给出一个二叉树,输出它的 ...
-
codevs 1501 二叉树最大宽度和高度x
题目描述 Description 给出一个二叉树,输出它的最大宽度和高度. 输入描述 Input Description 第一行一个整数n. 下面n行每行有两 ...
-
AC日记——二叉树最大宽度和高度 1501 codevs
1501 二叉树最大宽度和高度 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 题目描述 Description 给出一个二叉树,输出它的最大宽 ...
-
codevs1501 二叉树最大宽度和高度
难度等级:白银 1501 二叉树最大宽度和高度 题目描述 Description 给出一个二叉树,输出它的最大宽度和高度. 输入描述 Input Description 第一行一个整数n. 下面 ...
-
ACM题目————二叉树最大宽度和高度
http://codevs.cn/problem/1501/ 题目描述 Description 给出一个二叉树,输出它的最大宽度和高度. 输入描述 Input Description 第一行一个整 ...
-
[wikioi]二叉树最大宽度和高度
简单的DFS,用数组w记录每一层的宽度就行了,就是遇到一层就++.中间发现在C++里面,如果int未初始化就是用也是有异常的.还有二叉树的数组表示时,从1开始计数会比较好.还有后来学会了数组这样的初始 ...
-
1501 二叉树最大宽度和高度 (BFS+树的遍历)
题目:http://www.wikioi.com/problem/1501/ 给你一颗二叉树,求该数的宽和高, 首先求出树的高,直接进行二叉树遍历,能够得到二叉树的高 然后是得到宽,本人采用的是一层一 ...
-
Codevs 1501 二叉树的最大宽度和高度
1501 二叉树最大宽度和高度 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 题目描述 Description 给出一个二叉树,输出它的最大宽度和高度. 输入描 ...
-
二叉树 Java 实现 前序遍历 中序遍历 后序遍历 层级遍历 获取叶节点 宽度 ,高度,队列实现二叉树遍历 求二叉树的最大距离
数据结构中一直对二叉树不是很了解,今天趁着这个时间整理一下 许多实际问题抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显 ...
随机推荐
-
css div垂直居中
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/ ...
-
[C语言](二)01 获取Windows图形构件大小信息
SYSMETS.c #include <windows.h> #include "SYSMETS.H"//自定义的单元,所以用"",不是用<& ...
-
char引发的血案
char cc = 'j';cc = (char)(cc -32); //注意下,自动转型了System.out.println(cc);
-
MVC,jquery异步
创建一个Ajax控制器 using System; using System.Collections.Generic; using System.Linq; using System.Web; usi ...
-
Spring mvc系列一之 Spring mvc简单配置
Spring mvc系列一之 Spring mvc简单配置-引用 Spring MVC做为SpringFrameWork的后续产品,Spring 框架提供了构建 Web 应用程序的全功能 MVC 模块 ...
-
--css 控制文字多使用省略号
--css 控制文字多使用省略号.overflowPoint{ text-overflow:ellipsis;width: 200px;overflow: hidden;}<div class= ...
-
(译)package.json详解
原文链接 概述 本文囊括了所有package.json文件中你需要知道的细节.注意package.json必须是纯JSON的,而不仅仅是一个JavaScript对象字面量.该文件描述的很多行为都受np ...
-
nova相关操作的Request_Id的获取
在分析nova的众多log文件时,如nova-api,nova-scheduler,nova-compute等,其中的request id是串联起整个flow的关键词. 而通过nova instanc ...
-
node中npm安装模块的网络问题
最近使用node开发时,发现所有的依赖模块都安装不了啦,一直报错如下 rollbackFailedOptional: verb npm-session 5a4a66a1b8d06dc3 后来才发现是由 ...
-
MYSQL登录错误:mysqladmin: connect to server at ‘localhost’ failed
一.mysql登录错误 mysqladmin: connect to server at 'localhost' failed error: 'Access denied for user ...