Algorithm
Problem Name: 662. 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:
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:
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:
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
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
// BFS
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
if(!root) return 0;
int maxWidth = 1;
deque<pair < TreeNode*, int>>cur;
deque < pair;
if(p.first->left) next.push_back({p.first->left, p.second * 2});
if(p.first->right) next.push_back({p.first->right, p.second * 2 + 1});
if(cur.empty() && !next.empty()){
swap(cur, next);
maxWidth = max(maxWidth, cur.back().second - cur.front().second + 1);
}
}
return maxWidth;
}
};
// DFS
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
int maxWidth = 0;
vector<int>v;
DFS(root, v, 1, 0, maxWidth);
return maxWidth;
}
void DFS(TreeNode* root, vector<int>& v, int tag, int level, int& maxWidth){
if(!root) return;
if(v.size() == level) v.push_back(tag);
maxWidth = max(maxWidth, tag - v[level] + 1);
DFS(root->left, v, tag * 2, level + 1, maxWidth);
DFS(root->right, v, tag * 2 + 1, level + 1, maxWidth);
}
};
Input
Output
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int widthOfBinaryTree(TreeNode root) {
int maxWidth = 0;
Queue < TreeNode> queue = new LinkedList<>();
Map map = new HashMap<>();
map.put(root, 1);
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
int start = 0;
int end = 0;
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (i == 0) {
start = map.get(node);
}
if (i == size - 1) {
end = map.get(node);
}
if (node.left != null) {
map.put(node.left, map.get(node) * 2);
queue.add(node.left);
}
if (node.right != null) {
map.put(node.right, map.get(node) * 2 + 1);
queue.add(node.right);
}
}
maxWidth = Math.max(maxWidth, end - start + 1);
}
return maxWidth;
}
}
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const widthOfBinaryTree = function(root) {
const mins = [0]
let max = 0
dfs(root, 0, 0)
return max
// depth first search
function dfs(currentNode, depth, position) {
if (!currentNode) return
if (depth === mins.length) {
mins[depth] = position
}
const delta = position - mins[depth]
max = Math.max(max, delta + 1)
dfs(currentNode.left, depth + 1, delta * 2)
dfs(currentNode.right, depth + 1, delta * 2 + 1)
}
}
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def widthOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
dic, stack, res = {root: 1}, [root], 0
while any(stack):
tmp, mn ,mx = [], float("inf"), - float("inf")
for node in stack:
res = max(res, dic[stack[-1]] - dic[stack[0]] + 1)
if node.left: tmp, dic[node.left] = tmp + [node.left], dic[node] * 2 - 1
if node.right: tmp, dic[node.right] = tmp + [node.right], dic[node] * 2
stack = tmp
return res
Input
Output
#5 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
namespace LeetCode
{
public class _0662_MaximumWidthOfBinaryTree
{
public int WidthOfBinaryTree(TreeNode root)
{
return dfs(root, 0, 1, new Dictionary < int, int>(), new Dictionary<int, int>());
}
public int dfs(TreeNode root, int level, int order, IDictionary<int, int> start, IDictionary<int, int> end)
{
if (root == null) return 0;
if (start.Count == level)
{
start[level] = order;
end[level] = order;
}
else
end[level] = order;
int cur = end[level] - start[level] + 1;
int left = dfs(root.left, level + 1, 2 * order, start, end);
int right = dfs(root.right, level + 1, 2 * order + 1, start, end);
return Math.Max(cur, Math.Max(left, right));
}
}
}
Input
Output