#P1077. 寻找节点2
寻找节点2
题目描述
存在一棵有 n 个节点的有根树(1号节点为根),请你编写代码,按照深度优先遍历的顺序,找到深度为h的节点中的第一个叶子节点。
输入格式
第 1 行,包含两个整数 n和h,代表树的节点数量和指定深度。 第 2 行 ~ 第 n 行,每行包含两个整数 u 和 v,u 是 v 的父节点。
输出格式
仅一行,包含1整数。表示按照层序遍历方式找到的第h层 的第一个叶子节点。
样例1
5 2
1 2
1 5
2 3
2 4
5
样例解释
深度为2的节点有两个,分别是2号节点和5号节点,但2号节点不是叶子节点,所以输出5。
样例2
7 3
1 2
2 3
1 4
4 5
5 6
1 7
3
数据范围
1 ≤ n ≤ 1000,1 ≤ u, v ≤ n。 输入数据保证:只存在一棵树,树上所有节点均为 1 ~ n 中的数,h 大于1且小于等于树的总深度,第 h 层必然存在叶子节点。