当前没有测试数据。

给你一棵二叉树的根节点 root ，返回树的 最大宽度 。

树的 最大宽度 是所有层中最大的 宽度 。

每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。

题目数据保证答案将会在 32 位 带符号整数范围内。

• ​输入格式​：二叉树的层序遍历序列（用空格分隔，null表示空节点）
• ​输出格式​：一个整数，表示树的最大宽度

输入输出示例

示例1

输入： 1 3 2 5 3 null 9 输出： 4

示例2

输入： 1 3 2 5 输出： 2

示例3

输入： （直接回车） 输出： 0