力扣（LeetCode）
链接：662. 二叉树最大宽度
题目描述如下：
给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
题目数据保证答案将会在 32 位 带符号整数范围内。
示例 1：
输入：root = [1,3,2,5,3,null,9]
输出：4
解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。
示例 2：
输入：root = [1,3,2,5,null,null,9,6,null,7]
输出：7
解释：最大宽度出现在树的第 4 层，宽度为 7 (6,null,null,null,null,null,7) 。
示例 3：
输入：root = [1,3,2,5]
输出：2
解释：最大宽度出现在树的第 2 层，宽度为 2 (3,2) 。
提示：
- 树中节点的数目范围是 [1, 3000]
- -100 <= Node.val <= 100
解题思路：
使用层序遍历的方法找到每一层最左元素和最右元素按满二叉树排列时的编号，相减即为该层的宽度，返回最大宽度。
这里有一个小坑，按题目的描述元素的编号是可能会超出int的范围的，但是编号定义为int才能通过最后一个测试点，定义为long会报错，具体什么原因还未知。
Java代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
class Solution {
public int widthOfBinaryTree(TreeNode root) {
class theNode {
TreeNode root;
int number;
int height;
theNode(TreeNode root, int number, int height){
this.root=root;
this.number=number;
this.height=height;
}
}
int resutl = 0;
int level = 1;
int left=1,right=1;
Queue<theNode> queue = new LinkedList<theNode>();
queue.offer(new theNode(root,1,1));
while(!queue.isEmpty()){
theNode tmp = queue.poll();
if(tmp.height==level){
right=tmp.number;
if(right-left+1>resutl){
resutl=(right-left)+1;
}
}else{
level++;
if(right-left+1>resutl){
resutl=(right-left)+1;
}
left=tmp.number;
right=tmp.number;
}
if(tmp.root.left!=null){
queue.offer(new theNode(tmp.root.left,tmp.number*2,tmp.height+1));
}
if(tmp.root.right!=null){
queue.offer(new theNode(tmp.root.right,tmp.number*2+1,tmp.height+1));
}
}
if(right-left+1>resutl){
resutl=(right-left)+1;
}
return resutl;
}
}
|