BFS ，也就是广度优先遍历，类似层次遍历的方法（同上给每个节点编上号），求得每一层，把每一层的左右两端的编号进行相减。
class Solution {
public int widthOfBinaryTree(TreeNode root) {
if (root == null) return 0;
Map<TreeNode,Integer> map = new HashMap<>();//存储节点对应的下标
Queue<TreeNode> queue = new LinkedList<>();//通过队列实现bfs
//初始化
int max = 1;
zixun(root);
map.put(root,1);
while (!queue.isEmpty()) {
int start = map.get(queue.peek());//获取每层起始节点（即最左端点）的下标
int size = queue.size();
while (size > 0) {
TreeNode node = queue.poll();
size--;
int index = map.get(node);//获取此节点下标，用与给其的左右孩子确定下标
if (node.left != null) {
map.put(node.left,index*2);//确定左孩子下标
queue.offer(node.left);//节点入队
}
if (node.right != null) {
map.put(node.right,index*2 + 1);//确定右孩子下标
queue.offer(node.right);//节点入队
}
if(size == 0) max = Math.max(max,index - start + 1);//本层遍历结束，更新层宽最大值
}
}
return max;
}
}
DFS深度优先遍历，通过递归的方式实现，递归每层的记录带上层数，进行计算。
class Solution {
Map<Integer, Integer> map = new HashMap<>();
int ans;
public int widthOfBinaryTree(TreeNode root) {
dfs(root, 1, 0);
return ans;
}
void dfs(TreeNode root, int u, int depth) {
if (root == null) return ;
if (!map.containsKey(depth)) map.put(depth, u);
ans = Math.max(ans, u - map.get(depth) + 1);
u = u - map.get(depth) + 1;
dfs(root.left, u << 1, depth + 1);
dfs(root.right, u << 1 | 1, depth + 1);
}
}
链接：https://leetcode.cn/problems/maximum-width-of-binary-tree/solutions/1778862/by-ac_oier-33er/
来源：力扣（LeetCode）