定义：对于任意节点 $u$ ，假设它的左子树深度为 $L_u$ ，右子树深度为 $R_u$ ，那么经过 $u$ 的最长路径长度为 $L_u + R_u$ 。
全局直径：我们需要维护一个全局变量 $\text{diameter}$ ，初始化为 0。对树中每个节点 $u$ ，更新：

$\text{diameter} = \max(\text{diameter},L_u + R_u)$
递归计算深度：使用后序遍历，对于节点 $u$ ：

P3410.第2题-二叉树的直径

1000ms

Difficulty: 3

所属公司 : 大疆

算法与标签>DFS

题目内容

给定一棵二叉树序列，返回该树的直径。二叉树的直径指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 $root$ 。

两节点之间路径的长度由它们之间边数表示。

序列定义:输入序列是二叉树的层序遍历，其从上到下、从左到右依次将节点值入队(包含空节点，但序列尾部空节点会被省略)，非空节点为非 $0$ 值，空节点以 $0$ 值表示。

例 $1$ : 表示为：

$9$

$1\ 2\ 0\ 4\ 0\ 0\ 0\ 5$

第一行为序列长度，第二行为层序遍历序列

例 $2$ : 表示为：

$6$

$1\ 5\ 2\ 3\ 0\ 6$

注：给定的二叉树非空的合法序列，层序遍历序列长度 $<=500，-100<=$ 数值 $<=100$

输入层序遍历序列(见题干说明)

二叉树的直径

输入

9
1 2 0 3 4 0 0 0 5

输出

输入

预期输出（选填）