思路

1. 定义：对于任意节点 $u$，假设它的左子树深度为 $L_u$，右子树深度为 $R_u$，那么经过 $u$ 的最长路径长度为 $L_u + R_u$。

2. 全局直径：我们需要维护一个全局变量 $\text{diameter}$，初始化为 0。对树中每个节点 $u$，更新：

   $\text{diameter} = \max(\text{diameter},L_u + R_u)$

3. 递归计算深度：使用后序遍历，对于节点 $u$：

题目内容

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

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

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

例$1$: 表示为：

$9$

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

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

例$2$: 表示为：

$6$

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

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

输入描述

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

输出描述

二叉树的直径

样例1

输入

9
1 2 0 3 4 0 0 0 5

输出

3