题目：
思路:
使用BST遍历，与把二叉树打印成多行相似，将nodes的size 即为一层的节点个数，一层就是一个for !
给每个节点一个位置position值，其左右子节点的位置分别为 position*2 和 position*2+1
新建一个CustomNode类存如TreeNode以及对应的position
每一层的宽度: width=最右position-最左position+1
每一层（即一个for循环）用一个ArrayList装position，for循环结束后计算当前层的width
Java实现：
class Solution {
public int widthOfBinaryTree(TreeNode root) {
// 利用size分层
// 每一轮用list装position
Queue<CustomNode> nodes=new LinkedList<>();
int width=0;
if(root!=null){
nodes.add(new CustomNode(root,1)); // CustomNode需要new出来！
}
while(!nodes.isEmpty()){
// 每一层用list记录
// 每一轮for弹出node
// 每一次for用size分层
ArrayList<Integer> list=new ArrayList<>();
int size=nodes.size();
for(int i=0;i<size;i++){
CustomNode n=nodes.poll();
list.add(n.position);
if(n.node.left!=null){
nodes.add(new CustomNode(n.node.left,n.position*2));
}
if(n.node.right!=null){
nodes.add(new CustomNode(n.node.right,n.position*2+1));
}
}
// 每层结束算宽度= 每一层的最大position -最小position +1
width=Math.max(width, list.get(list.size()-1) - list.get(0)+1);
}
return width;
}
}
class CustomNode{
TreeNode node;
int position;
public CustomNode(TreeNode node,int position){
this.node=node;
this.position=position;
}
}
注意：
计算最右position 用的是list.get(list.size()-1)， list存的是当前层的position，中间有null也会算上，而nodes存的是下一层的所有节点，nodes.size()是节点个数 ≠ 宽度
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89304.html
