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

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

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

二叉树的高度

题目描述

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

输入描述

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

输出描述

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

示例

输入

5

0 1

0 2

1 3

1 4

输出

3

解析

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

代码

#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;
}

运行结果

(0)

相关推荐

  • 已知完全二叉树有30个节点 则整个二叉树有()个度为1的节点。

    已知完全二叉树有30个节点,则整个二叉树有()个度为1的节点. A.0 B.1 C.2 D.不确定 参考答案 参考答案:B 完全二叉树:除了最外层,其余层上的节点数目都达到最大值,而第h层上的节点集中 ...

  • ORB-SLAM中四叉树管理角点

    四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构.它将已知范围的空间等分成四个相等的子空间,如此递归下去,直至树的层次达到一定深度或者满足某种要求后停止分割. 四叉树对于区域查询,效率比较高 ...

  • 剑指offer之求二叉树中两个节点的最低共同父节点

    剑指offer之求二叉树中两个节点的最低共同父节点

  • ​LeetCode刷题实战144:二叉树的前序遍历

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战310:最小高度树

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

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

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

  • 【黑客数学·每日一题】暑假期间“每日一题”汇总版

    各位黑客伙伴们: 大家好!随着暑期的结束,我们迎来了崭新的学期,"每日一题"的发布时间也正式恢复为常规的每周一到周五的下午(一周五期). 有部分黑客伙伴们在暑假安排了各种各样精彩活 ...

  • 每日一题 C++版(走迷宫)

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

  • 每日一题 C++版(汽水瓶)

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

  • 每日一题 C++版(简单密码)

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

  • 每日一题 C++版(分类有效的IP地址和掩码)

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

  • 每日一题 C++版(坐标移动)

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

  • 每日一题C++版(组成最大的数)

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

  • 每日一题C++版(电话号码分身)

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