求二叉树最宽的层有多少个节点求二叉树最宽的层有多少个节

一、思路：在按层遍历的基础上进行改写。
（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 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 queue = new LinkedList<>(); queue.add(head); // key：节点，value：节点在哪一层 HashMap 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; }

【求二叉树最宽的层有多少个节点】本文全部代码：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/binarytree/TreeMaxWidth.java