662.Maximum Width of Binary Tree
===
###### tags: `Medium`,`Tree`,`BFS`,`DFS`
[662. Maximum Width of Binary Tree](https://leetcode.com/problems/maximum-width-of-binary-tree/)
### 題目描述
Given the `root` of a binary tree, return *the **maximum width** of the given tree.*
The **maximum width** of a tree is the maximum **width** among all levels.
The **width** of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.
It is **guaranteed** that the answer will in the range of a **32-bit** signed integer.
### 範例
**Example 1:**
![](https://assets.leetcode.com/uploads/2021/05/03/width1-tree.jpg)
```
Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).
```
**Example 2:**
![](https://assets.leetcode.com/uploads/2022/03/14/maximum-width-of-binary-tree-v3.jpg)
```
Input: root = [1,3,2,5,null,null,9,6,null,7]
Output: 7
Explanation: The maximum width exists in the fourth level with length 7 (6,null,null,null,null,null,7).
```
**Example 3:**
![](https://assets.leetcode.com/uploads/2021/05/03/width3-tree.jpg)
```
Input: root = [1,3,2,5]
Output: 2
Explanation: The maximum width exists in the second level with length 2 (3,2).
```
**Constraints**:
* The number of nodes in the tree is in the range `[1, 3000]`.
* -100 <= `Node.val` <= 100
### 解答
#### Python
```python=
class Solution:
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
q = deque([(root, 0, 0)])
dic = defaultdict(list)
while q:
node, level, idx = q.popleft()
dic[level].append(idx)
if node.left:
q.append((node.left, level + 1, 2 * idx))
if node.right:
q.append((node.right, level + 1, 2 * idx + 1))
max_width = 0
for nodes in dic.values():
width = nodes[-1] - nodes[0] + 1
max_width = max(max_width, width)
return max_width
```
> [name=Ron Chen][time=Thu, Apr 20, 2023]
#### Javascript
```javascript=
function widthOfBinaryTree(root) {
let max = 1;
const queue = [[root, 0]];
while (queue.length) {
const n = queue.length;
if (n === 1) queue[0][1] = 1;
const [left, right] = [queue[0][1], queue[n - 1][1]];
max = Math.max(max, right - left + 1);
for (let i = 0; i < n; i++) {
const [node, index] = queue.shift();
if (node.left) queue.push([node.left, index * 2]);
if (node.right) queue.push([node.right, index * 2 + 1]);
}
}
return max;
}
```
> [name=Marsgoat][time=Thu, Apr 20, 2023]
### Reference
[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)