二叉树最大宽度 题目描述 给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。 每一

二叉树最大宽度

题目描述

b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。

输入

b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第一行一个整数n，表示结点数b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第二行n个整数，空格分隔，-1表示无结点

输出

b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
一个整数，表示树的最大宽度

样例输入

7
1 3 2 5 3 -1 9

样例输出 

4

提示

b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
样例一解释：b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入: b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
           1b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
         /   \b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
        3     2b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
       / \     \  b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
      5   3     9 b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出: 4b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
样例二b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入：b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
5b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1 3 -1 5 3b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出：b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
2b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
样例二解释：b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入: b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
          1b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
         /  b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
        3    b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
       / \       b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
      5   3     b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出: 2b0S100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。