每日一题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;
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-08-27，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读