二叉树的最大深度

题目描述

给定一棵二叉树的根节点 root，请返回其最大深度。

二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

输入格式

第一行输入一个整数 n，表示二叉树层序序列的长度。

第二行输入 n 个字符串，表示二叉树的层序遍历结果，其中：

• 非 null 字符串表示该节点的整数值；
• null 表示该位置为空节点。

保证输入序列能够唯一确定一棵二叉树，且根节点非空。

输出格式

输出一个整数，表示二叉树的最大深度。

数据范围

1 <= n <= 10^4

-100 <= Node.val <= 100

样例 1

输入

7
3 9 20 null null 15 7

输出

3

样例 2

输入

3
1 null 2

输出

2