LG#P4913. 二叉树深度

二叉树深度

题目描述

\hspace{15pt}给定一棵有 nn 个节点的二叉树,节点编号为 1∼n1\sim n,根节点为 11。每个节点至多有一个左子节点和一个右子节点。

\hspace{15pt}请计算这棵二叉树的深度。根节点所在层为第 11 层,一个节点的子节点所在层比它多 11;树的深度为所有节点所在层数的最大值。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦106)n\left(1\leqq n\leqq10^6\right),代表节点数量。

\hspace{15pt}此后 nn 行,第 ii 行输入两个整数 li,ri(0≦li,ri≦n)l_i,r_i\left(0\leqq l_i,r_i\leqq n\right),分别代表节点 ii 的左、右子节点编号。数值 00 表示对应子节点不存在,叶节点输入 0 00\ 0。

\hspace{15pt}保证这些记录构成一棵以节点 11 为根的二叉树,所有节点都能从根到达;节点编号不保证按层次排列。

输出格式

\hspace{15pt}输出一个整数,代表二叉树的深度。

测试样例

7
2 7
3 6
4 5
0 0
0 0
0 0
0 0
4

样例 1 解释

\hspace{15pt}从根节点依次经过 1,2,3,41,2,3,4,共经过 44 层。没有更深的节点,因此答案为 44。

5
0 3
0 0
5 2
0 0
4 0
4