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

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

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

树的高度

题目描述

现在有一个由有序数对组成的树,树的节点都是用数字表示,现在给定这棵树上所有的父子关系,求这棵树的高度

输入描述:

输入的第一行表示节点的个数n(1 ≤ n ≤ 1000,节点的编号为0到n-1)组成,

下面是n-1行,每行有两个整数,第一个数表示父节点的编号,第二个数表示子节点的编号

输出描述:

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

示例

输入

5

0 1

0 2

1 3

1 4

输出

3

解析

其实这里面的树,也就是链表。如果可以使用容器将同一高度的节点放在一个容器内,这个高度内的节点的子节点放在下一层绒球内。父节点放在上一层容器。由于我们不能总是先发现父节点,因此这个容器也会在首段插入数据。因此我们需要使用两端插入数据比较快的容器,因此我们选用list容器。而这个容器内的元素也应该是一个容器(为了方便我们插入同样高度的新节点)。

这样首先我们就在每一层中寻找父节点,如果找到,就将其子节点插入(存入)下一层;如果没有找到,我们就在每一层中寻找子节点,如果找到,就将其父节点插入(存入)上一层,并且将这个节点从需要插入“树”中的数据里面删除。最后只要看这个list容器的size就可以了。

代码

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
 int index;
 while (cin >> index)
 {
   list<vector<int>> joint;
   list<vector<int>> tree;
   for (int i = 0; i < index-1; i++)
   {
     vector<int> subjoint;
     int father, son;
     cin >> father >> son;
     subjoint.push_back(father);
     subjoint.push_back(son);
     joint.push_back(subjoint);
     if (tree.empty())
     {
       vector<int> father_t;
       father_t.push_back(father);
       vector<int> son_t;
       son_t.push_back(son);
       tree.push_back(father_t);
       tree.push_back(son_t);
     }
   }
   while (!joint.empty())
   {
     for (auto i = joint.cbegin(); i != joint.cend(); )
     {
       bool add = false;
       for (auto m = tree.begin(); m != tree.end(); m++)
       {
         int father = (*i)[0];
         int son = (*i)[1];
         auto findfather = find((*m).cbegin(), (*m).cend(), father);
         auto findson = find((*m).cbegin(), (*m).cend(), son);
         auto lastone = tree.cend();
         lastone--;
         if (findfather != (*m).cend())
         {
           if (m == lastone)
           {
             vector<int> subjoint;
             subjoint.push_back(son);
             tree.push_back(subjoint);
             i = joint.erase(i);
             add = true;
             break;
           }
           if (m != lastone)
           {
             m++;
             (*m).push_back(son);
             m--;
             i = joint.erase(i);
             add = true;
             break;
           }
         }
         else if (findson != (*m).cend())
         {
           if (m == tree.begin())
           {
             vector<int> subjoint;
             subjoint.push_back(father);
             tree.push_front(subjoint);
             i = joint.erase(i);
             add = true;
             break;
           }
           if (m == tree.begin())
           {
             m++;
             (*m).push_back(father);
             m--;
             i = joint.erase(i);
             add = true;
             break;
           }
         }
       }
       if (!add)
       {
         i++;
       }
     }
   }
   cout << tree.size() << endl;
 }
 return 0;
}
(0)

相关推荐

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

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

  • "有其父必有其子",英语怎么说?| 1分钟英语Ⅱ

    版权所有 未经授权不得转载 第二季 第46期 (每周一到五更新) like father, like son 有其父必有其子 ►含义: sons are very similar to their f ...

  • 34小麦头日常生长记录分析:

    商秧变法,美国佬,苏联大哥中共制造原子弹,姜维,钟会,邓艾,阿斗,司马昭,父子之情,司马炎,探索,继承,创新,小峰哥,姐,他儿子,曹娟,曹远,书法,佳兴,我,曹大姐,不适应变适应,笔头,随笔,日记,错 ...

  • Father and Son

    I am your father, I am your playmate, I am your hero, I am your teammate, I am your teacher, I am yo ...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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