算法-完全二叉树的最大宽度和高度

╰半夏微凉° 2022-08-04 13:34 140阅读 0赞

![20150829002922818][]

题目描述 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

提示:

默认第一个是根节点

以输入的次序为编号

2-N+1行指的是这个节点的左孩子和右孩子

代码如下:

#include "stdio.h" 
    #include "string.h"   
    int a[1000][2],b[1000];  
    int i,n,x,y;   
    void dfs(int i,int k)  
    {  
        b[k]=b[k]+1;  
        if(k>x)  x=k;  
        if(a[i][1]!=0)  dfs(a[i][1],k+1);  
        if(a[i][2]!=0)  dfs(a[i][2],k+1);  
    }  
    int main()  
    {  
        scanf("%d",&n);  
        memset(a,0,sizeof(a));  
        memset(b,0,sizeof(b));  
        for(i=1;i<=n;i++)  
            scanf("%d%d",&a[i][1],&a[i][2]);  
        x=0;  
        dfs(1,1);  
        y=0;  
        for(i=1;i<1000;i++)  
            if(b[i]>y)   y=b[i];  
        printf("%d %d",y,x);  
        return 0;  
    }

[20150829002922818]: /images/20220731/3c480a39abb4419888cf01e7cb9b0920.png

发表评论取消回复

表情：

评论列表（有 0 条评论，140人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode：二叉树最大宽度

class Solution { public: struct node { TreeNode* root; ...

「爱情、让人受尽委屈。」/ 2024年04月17日 19:11/ 0 赞/ 84 阅读

相关查找二叉树、完全二叉树、线索二叉树、最优二叉树

文章目录前言一、查找二叉树（二叉排序树）二、完全二叉树三、线索二叉树四、最优二叉树（哈夫曼树） ----------------

痛定思痛。/ 2023年10月01日 21:38/ 0 赞/ 67 阅读

相关二叉树深度和高度_二叉树的高度和深度

![208b9eac8e4029f24bebf06a7ac44c80.png][] 二叉树深度和高度 In this tutorial, we will learn how

忘是亡心i/ 2022年12月07日 12:56/ 0 赞/ 210 阅读

相关 2021-02-09 | 662. 二叉树最大宽度

1. 题目描述给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一

逃离我推掉我的手/ 2022年11月05日 03:19/ 0 赞/ 196 阅读

相关 LeetCode | 0662. 二叉树最大宽度【Python】

问题 [力扣][Link 1] 给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree

痛定思痛。/ 2022年11月03日 10:36/ 0 赞/ 186 阅读

相关 662. 二叉树最大宽度

> > > 给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点

谁践踏了优雅/ 2022年10月07日 15:50/ 0 赞/ 167 阅读

相关算法-完全二叉树的最大宽度和高度

![20150829002922818][] 题目描述 Description 给出一个二叉树，输出它的最大宽度和高度。输入描述 Inpu

╰半夏微凉°/ 2022年08月04日 13:34/ 0 赞/ 141 阅读

相关完全二叉树和满二叉树的区别

堆的话一般都是用完全二叉树来实现的，比如大堆和小堆。一个树节点的度数就是这个树节点有多少子节点，和树的深度意义不同。依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合

谁借莪１个温暖的怀抱￠/ 2022年07月31日 16:05/ 0 赞/ 257 阅读

相关满二叉树和完全二叉树

满二叉树一棵深度为k，且有2^k-1个节点的树是满二叉树。另一种定义：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。这两种定义是等价的。

快来打我*/ 2022年02月25日 09:42/ 0 赞/ 322 阅读

相关二叉树最大宽度和高度

[傳送門][Link 1] 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 题目描述 Description 给出一个二叉树

约定不等于承诺〃/ 2021年12月14日 12:47/ 0 赞/ 280 阅读