一、思路：
在按层遍历的基础上进行改写。
（1）准备currentLevelEnd（表示当前层的结束节点）、nextLevelEnd（表示下一层的结束节点）、currentWeight（表示当前层的宽度）、maxWeight（表示最大宽度）四个变量。
（2）currentLevelEnd修改为二叉树的头节点（其他均为默认值），头节点入队列。
（3）从队列中弹出一个节点，每出队一个节点则currentWeight加一，出队节点有左孩子则左孩子入队，有右孩子则右孩子入队，有节点入队则将nextLevelEnd修改为当前入队的节点（为下一层查找做准备）。
（4）判断第3步出队的节点是否等于currentLevelEnd。
是，则修改maxWeight为当前最大宽度，currentWeight重置，currentLevelEnd修改为nextLevelEnd，nextLevelEnd重置；
否，则继续执行第3步。
（5）一直执行第3、4步，直到队列为空。
/**
* @author Java和算法学习：周一
*/
public static int treeMaxWidth(Node head) {
if (head == null) {
return 0;
}
Queue<Node> queue = new LinkedList<>();
Node currentLevelEnd = head;
Node nextLevelEnd = null;
int currentWidth = 0;
int maxWidth = 0;
queue.offer(head);
while (!queue.isEmpty()) {
Node current = queue.poll();
// 每次从队列中弹出节点时，当前层的宽度都加一
currentWidth++;
// 有孩子节点入队时就修改下一层的结束节点
if (current.left != null) {
queue.offer(current.left);
nextLevelEnd = current.left;
}
if (current.right != null) {
queue.offer(current.right);
nextLevelEnd = current.right;
}
// 如果当前出队的节点是当前层的结束节点
if (current == currentLevelEnd) {
// 修改最大宽度
maxWidth = Math.max(maxWidth, currentWidth);
// 当前层宽度重置
currentWidth = 0;
// 当前层的结束节点修改，表明下一次循环时开始统计下一层的宽度
currentLevelEnd = nextLevelEnd;
// 下一层结束节点重置
nextLevelEnd = null;
}
}
return maxWidth;
}
二、对数器源码
/**
* 对数器方法
*
* @author Java和算法学习：周一
*/
public static int treeMaxWidth1(Node head) {
if (head == null) {
return 0;
}
Queue<Node> queue = new LinkedList<>();
queue.add(head);
// key：节点，value：节点在哪一层
HashMap<Node, Integer> levelMap = new HashMap<>(16);
levelMap.put(head, 1);
// 当前来到哪一层
int curLevel = 1;
// 当前层的宽度
int curLevelWidth = 0;
// 最大宽度
int max = 0;
while (!queue.isEmpty()) {
Node cur = queue.poll();
int curNodeLevel = levelMap.get(cur);
if (cur.left != null) {
levelMap.put(cur.left, curNodeLevel + 1);
queue.add(cur.left);
}
if (cur.right != null) {
levelMap.put(cur.right, curNodeLevel + 1);
queue.add(cur.right);
}
// 当前节点还是在当前层
if (curNodeLevel == curLevel) {
curLevelWidth++;
} else {
// 当前层已经遍历完毕
max = Math.max(max, curLevelWidth);
// 来到下一层
curLevel++;
// 当前节点已经是下一层的了，也就是下一层已经有一个节点了，宽度自然是1
curLevelWidth = 1;
}
}
// 最后一层的宽度没有和max比较，所以这里要再比较一次
max = Math.max(max, curLevelWidth);
return max;
}
