前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >每日一题C++版(二叉树的高度)

每日一题C++版(二叉树的高度)

作者头像
小白学视觉
发布2019-10-24 01:01:38
5390
发布2019-10-24 01:01:38
举报
文章被收录于专栏:深度学习和计算机视觉

编程是很多偏计算机、人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”,通过每天一道编程题目来强化和锻炼自己的编程能力(最起码不会忘记编程)

特别说明:编程题来自“牛客网”和“领扣”以及热心小伙伴的题目。由于小白有时想锻炼某一类编程方法,所以提供的代码不一定是最优解,但是本文提供的编程代码均为通过测试代码。

二叉树的高度

题目描述

现在有一棵合法的二叉树,树的节点都是用数字表示,现在给定这棵树上所有的父子关系,求这棵树的高度。

输入描述

输入的第一行表示节点的个数n(1 ≤ n ≤ 1000,节点的编号为0到n-1)组成,下面是n-1行,每行有两个整数,第一个数表示父节点的编号,第二个数表示子节点的编号。

输出描述

输出树的高度,为一个整数

示例

输入

5

0 1

0 2

1 3

1 4

输出

3

解析

本题和树的高度很像,但是题目上有区别,这道题的关键是说这是一个标准的二叉树,也就是说每个节点只能连接两个子节点,但是写出来程序之后发现通过率很低,原因是因为输入的测试数据中具有分支,因此需要对这些分支砍掉。

代码

代码语言:javascript
复制
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n,H = 1;
    int i = 0;
    int f,c, h;
    vector<int> nodes(1000, 0);    //有效节点的高度
    nodes[0] = 1; // 题目说了至少有一个节点,高度只是是1
    vector<int> childnum(1000, 0); //记录节点的孩子数量
    cin >> n;
    while(--n){
        cin >> f >> c;
        //父节点不存在 或者 父节点已有两个子节点 就跳过
        if(nodes[f]==0 || childnum[f] == 2)
            continue;
        childnum[f] += 1;
        h = nodes[f] + 1;
        nodes[c] = h;
        if(h > H) H = h;
    }
    cout << H;
    return 0;
}

运行结果

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-08-31,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 小白学视觉 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 二叉树的高度
    • 题目描述
      • 解析
        • 代码
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档