思路：
刚开始理解错了题目：以为求每一层的节点个数，然后求最大值。
于是有了：所有层中的最大节点数（声明了一个class包含了每个节点的层数，然后用Deque 模拟队列进行一次层次遍历，每次插入新的节点时，将父节点的layer+1赋值给子节点，然后将当前层的节点数+1，这里用了一个数组layers记录（长度我没有算，后面其实可以计算二叉树的深度O(logn)，定义数组长度），最后可以遍历数组layers,找最大值）
class Solution { class NodeLayer{ TreeNode treeNode; int layer; public NodeLayer(TreeNode treeNode, int layer){ this.treeNode = treeNode; this.layer = layer; } } // 先计算每一层的所有数量，取最大值 public int widthOfBinaryTree(TreeNode root) { if(root == null){ return 0; } return maxWidth(root); } public int maxWidth(TreeNode root){ // 假设最大有100层。 int[] layers = new int[100]; Deque<NodeLayer> deque = new ArrayDeque<>(); deque.addLast(new NodeLayer(root,0)); // 先写一个层次遍历 while(!deque.isEmpty()){ NodeLayer temp = deque.pollFirst(); // System.out.println(temp.treeNode.val); layers[temp.layer]+=1; if(temp.treeNode.left != null){ deque.addLast(new NodeLayer(temp.treeNode.left,temp.layer+1)); } if(temp.treeNode.right != null){ deque.addLast(new NodeLayer(temp.treeNode.right,temp.layer+1)); } } int max = 0; for(int i=0; i<10; i++){ max = Math.max(max,layers[i]); } return max; } }
发现问题后，我第一时间想到了双指针，每次指向左和右
还是有问题，因为找不到下一层的第一个节点，最后想到了利用index找
于是有了下面的方法。
1.首先我在之前的类中添加定义了一个值index 用于保存当前节点的index，这样我只需找到每一层最前和最后的index，相减加一即可得到最终解。
我利用一个数组layers_width[]保存每一层的宽度（当换层的时候，也就是上一个节点的layer与当前节点的layer不一样的时候，更新上一层的宽度和当前层的index），
用上一个节点(lastNode.index - layers_width[lastNode.layer] +1)上一层第一个节点的index 与 最后一个节点的index的差加一。然后将当前节点temp的index保存到当前层的位置：layers_width[temp.layer] = temp.index，下次就只需要用最后一个节点减就可以了。
2.中途出现了一个bug，是因为我将最后的边界条件放在了while里面，我判断deque为null时启动，但是该条件不止触发了一次，排查了很久。
3.完成后我对初始化的数组进行了优化：计算二叉树的深度来代替layers_width的长度（之前是随便设置了一个大数值，太小的话有的测试用例不过，太大浪费空间和时间）。后来发现不需要使用数组保存，只需要定义一个变量保存上一层的第一个节点的index:lastLayerFirstIndex（也不用计算二叉树深度了）。每次换层只需要比较大小并更新上一层的长度（lastNode.index - lastLayerFirstIndex +1）与当前最大长度max，然后更新lastLayerFirstIndex 为当前节点temp的index。
4.循环结束后，再更新一次max。这是由于最后一个节点如果没有换层，导致最后一层的宽度没有计算，所以需要在循环外进行一次更新max。
class Solution { class NodeLayer{ TreeNode treeNode; int layer; int index; public NodeLayer(TreeNode treeNode, int layer, int index){ this.treeNode = treeNode; this.layer = layer; this.index = index; } } public int widthOfBinaryTree(TreeNode root) { if(root == null){ return 0; } return maxWidth(root); } public void maxDepth(TreeNode node, int depth, int[] max){ if(node.left == null && node.right == null){ max[0] = Math.max(max[0], depth); } if(node.left != null){ maxDepth(node.left, depth+1, max); } if(node.right != null){ maxDepth(node.right, depth+1, max); } } public int maxWidth(TreeNode root){ // // 先求深度 // int[] depth = new int[1]; // maxDepth(root, 1, depth); // //深度 // int len = depth[0]; // // int len = 4000; // int[] layers_width = new int[len]; int lastLayerFistIndex=0; Deque<NodeLayer> deque = new ArrayDeque<>(); NodeLayer first = new NodeLayer(root,0,0); deque.addLast(first); int max = 1; // 定义一个指向上一个节点的指针 NodeLayer lastNode=first; // 先写一个层次遍历 while(!deque.isEmpty()){ NodeLayer temp = deque.pollFirst(); // 判断是否换层。如果换层就更新层宽度，最后一个节点的坐标减第一个的坐标 // System.out.println(temp.layer); if(lastNode.layer != temp.layer){ // // 更新上一层宽度 // layers_width[lastNode.layer] = lastNode.index-layers_width[lastNode.layer] +1; // max = Math.max(lastNode.index-layers_width[lastNode.layer] +1,max); max = Math.max(lastNode.index-lastLayerFistIndex +1,max); // 更新当前层第一个节点 // layers_width[temp.layer] = temp.index; lastLayerFistIndex = temp.index; } lastNode = temp; if(temp.treeNode.left != null){ deque.addLast(new NodeLayer(temp.treeNode.left,temp.layer+1,temp.index*2+1)); } if(temp.treeNode.right != null){ deque.addLast(new NodeLayer(temp.treeNode.right,temp.layer+1,temp.index*2+2)); } } // 如果最后一次没有发生层级改变 // layers_width[lastNode.layer] = lastNode.index-layers_width[lastNode.layer] +1; // max = Math.max(lastNode.index-layers_width[lastNode.layer] +1,max); max = Math.max(lastNode.index-lastLayerFistIndex +1,max); // for(int i=0; i<len ;i++){ // // System.out.print(layers_width[i]+" "); // max = Math.max(max,layers_width[i]); // } return max; } }
原文：https://www.cnblogs.com/wsZzz1997/p/14701559.html