Codevs 1051 二叉树最大宽度和高度

时间:2022-09-09 13:33:48

1501 二叉树最大宽度和高度

 时间限制: 1 s
 空间限制: 128000 KB
 题目等级 : 白银 Silver
 
 
 
题目描述 Description

给出一个二叉树,输出它的最大宽度和高度。

输入描述 Input Description

第一行一个整数n。

下面n行每行有两个数,对于第i行的两个数,代表编号为i的节点所连接的两个左右儿子的编号。如果没有某个儿子为空,则为0。

输出描述 Output Description

输出共一行,输出二叉树的最大宽度和高度,用一个空格隔开。

样例输入 Sample Input

5

2 3

4 5

0 0

0 0

0 0

样例输出 Sample Output

2 3

数据范围及提示 Data Size & Hint

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 二叉树最大宽度和高度的更多相关文章

  1. codevs——1501 二叉树最大宽度和高度

    1501 二叉树最大宽度和高度  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 白银 Silver 题解       题目描述 Description 给出一个二叉树,输出它的 ...

  2. codevs 1501 二叉树最大宽度和高度x

                         题目描述 Description 给出一个二叉树,输出它的最大宽度和高度. 输入描述 Input Description 第一行一个整数n. 下面n行每行有两 ...

  3. AC日记——二叉树最大宽度和高度 1501 codevs

    1501 二叉树最大宽度和高度  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 白银 Silver     题目描述 Description   给出一个二叉树,输出它的最大宽 ...

  4. codevs1501 二叉树最大宽度和高度

    难度等级:白银    1501 二叉树最大宽度和高度 题目描述 Description 给出一个二叉树,输出它的最大宽度和高度. 输入描述 Input Description 第一行一个整数n. 下面 ...

  5. ACM题目————二叉树最大宽度和高度

    http://codevs.cn/problem/1501/   题目描述 Description 给出一个二叉树,输出它的最大宽度和高度. 输入描述 Input Description 第一行一个整 ...

  6. &lbrack;wikioi&rsqb;二叉树最大宽度和高度

    简单的DFS,用数组w记录每一层的宽度就行了,就是遇到一层就++.中间发现在C++里面,如果int未初始化就是用也是有异常的.还有二叉树的数组表示时,从1开始计数会比较好.还有后来学会了数组这样的初始 ...

  7. 1501 二叉树最大宽度和高度 (BFS&plus;树的遍历)

    题目:http://www.wikioi.com/problem/1501/ 给你一颗二叉树,求该数的宽和高, 首先求出树的高,直接进行二叉树遍历,能够得到二叉树的高 然后是得到宽,本人采用的是一层一 ...

  8. Codevs 1501 二叉树的最大宽度和高度

    1501 二叉树最大宽度和高度 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 题目描述 Description 给出一个二叉树,输出它的最大宽度和高度. 输入描 ...

  9. 二叉树 Java 实现 前序遍历 中序遍历 后序遍历 层级遍历 获取叶节点 宽度 ,高度,队列实现二叉树遍历 求二叉树的最大距离

    数据结构中一直对二叉树不是很了解,今天趁着这个时间整理一下 许多实际问题抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显 ...

随机推荐

  1. css div垂直居中

    <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/ ...

  2. &lbrack;C语言&rsqb;(二)01 获取Windows图形构件大小信息

    SYSMETS.c #include <windows.h> #include "SYSMETS.H"//自定义的单元,所以用"",不是用<& ...

  3. char引发的血案

    char cc = 'j';cc = (char)(cc -32); //注意下,自动转型了System.out.println(cc);

  4. MVC&comma;jquery异步

    创建一个Ajax控制器 using System; using System.Collections.Generic; using System.Linq; using System.Web; usi ...

  5. Spring mvc系列一之 Spring mvc简单配置

    Spring mvc系列一之 Spring mvc简单配置-引用 Spring MVC做为SpringFrameWork的后续产品,Spring 框架提供了构建 Web 应用程序的全功能 MVC 模块 ...

  6. --css 控制文字多使用省略号

    --css 控制文字多使用省略号.overflowPoint{ text-overflow:ellipsis;width: 200px;overflow: hidden;}<div class= ...

  7. &lpar;译&rpar;package&period;json详解

    原文链接 概述 本文囊括了所有package.json文件中你需要知道的细节.注意package.json必须是纯JSON的,而不仅仅是一个JavaScript对象字面量.该文件描述的很多行为都受np ...

  8. nova相关操作的Request&lowbar;Id的获取

    在分析nova的众多log文件时,如nova-api,nova-scheduler,nova-compute等,其中的request id是串联起整个flow的关键词. 而通过nova instanc ...

  9. node中npm安装模块的网络问题

    最近使用node开发时,发现所有的依赖模块都安装不了啦,一直报错如下 rollbackFailedOptional: verb npm-session 5a4a66a1b8d06dc3 后来才发现是由 ...

  10. MYSQL登录错误:mysqladmin&colon; connect to server at &OpenCurlyQuote;localhost’ failed

    一.mysql登录错误 mysqladmin: connect to server at 'localhost' failed       error: 'Access denied for user ...