#1518. 徐老师的转换二叉树
-
ID: 1518
Type: Default
1000ms
256MiB
Tried: 11
Accepted: 2
Difficulty: 10
Uploaded By:
sulaoshi
Tags> 徐老师的转换二叉树
说明
徐老师最近学习了二叉树的遍历序列知识，但是毕竟不是所有的树都叫二叉树
这让徐老师非常头疼，于是他自己自创了一种 `二叉树转换法`
可以把一棵非二叉树用这种方法转换成一棵二叉树！
1. 徐老师会从根节点 $root$ 出发，用递归的形式遍历每个节点
2. 当遍历到节点 $A$ 时，徐老师会列出 $A$ 的所有兄弟节点 $x$，以及 $A$ 的所有孩子节点 $y$
3. 接着随机选择一个孩子节点 $y1$ 成为 $A$ 的左儿子，再随机选择一个兄弟节点 $x1$ 成为 $A$ 的右孩子
4. 递归遍历刚才选出的两个节点
但是显然，这种转换方式会构造出非常多不同形态的二叉树
为了不浪费空间，徐老师希望转换出来的二叉树深度尽可能小
他想知道在给定一棵树的情况下，构造出的树深度最小是多少？
输入格式
输入第一行一个整数 $n$ 表示这棵树的节点数量
接下来一行包含 $n - 1$ 个数字，分别表示 $2 \sim n$ 每个节点的父亲节点编号
题目保证第 $i$ 个节点的父亲编号均小于 $i$
对于 $20\%$ 的测试数据满足：$n \leq 10$
对于 $50\%$ 的测试数据满足：$n \leq 500$
对于 $100\%$ 的测试数据满足：$n \leq 100000$
输出格式
输出一个整数，表示这棵树用 `二叉树转换法` 转换成二叉树后最小的深度
样例
10
1 1 1 2 3 4 4 5 75提示
$1$ 选 $2$ 作为左儿子，$1$ 没有兄弟，所以没有右儿子
$2$ 选 $5$ 作为左儿子，选 $4$ 作为右儿子
$5$ 选 $9$ 作为左儿子，$5$ 没有兄弟，所以没有右儿子
$4$ 选 $7$ 作为左儿子，选 $3$ 作为右儿子
$7$ 选 $10$ 作为左儿子，选 $8$ 作为右儿子
$3$ 选 $6$ 作为左儿子，此时 $3$ 已经没有兄弟节点了，所以没有右儿子