Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/662.html
662. Maximum Width of Binary Tree (Medium)
Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.
The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.
Example 1:
Input:
1
/ \
3 2
/ \ \
5 3 9
Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).
Example 2:
Input:
1
/
3
/ \
5 3
Output: 2
Explanation: The maximum width existing in the third level with the length 2 (5,3).
Example 3:
Input:
1
/ \
3 2
/
5
Output: 2
Explanation: The maximum width existing in the second level with the length 2 (3,2).
Example 4:
Input:
1
/ \
3 2
/ \
5 9
/ \
6 7
Output: 8
Explanation:The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).
Note: Answer will in the range of 32-bit signed integer.
Companies:
Bloomberg, Microsoft
Related Topics:
Tree
Solution 1. Pre-order Traversal
// OJ: https://leetcode.com/problems/maximum-width-of-binary-tree/
// Time: O(N)
// Space: O(H)
class Solution {
typedef unsigned long long ULL;
vector<vector<ULL>> v;
ULL ans = 0;
void dfs(TreeNode *node, int lv, ULL nodeId) {
if (!node) return;
if (v.size() <= lv) v.push_back({ULLONG_MAX, 0});
v[lv][0] = min(v[lv][0], nodeId);
v[lv][1] = max(v[lv][1], nodeId);
ans = max(ans, v[lv][1] - v[lv][0] + 1);
dfs(node->left, lv + 1, 2 * nodeId);
dfs(node->right, lv + 1, 2 * nodeId + 1);
}
public:
int widthOfBinaryTree(TreeNode* root) {
if (!root) return 0;
dfs(root, 0, 0);
return ans;
}
};
Solution 1. Level-order Traversal
// OJ: https://leetcode.com/problems/maximum-width-of-binary-tree/
// Time: O(N)
// Space: O(N)
class Solution {
typedef unsigned long long ULL;
public:
int widthOfBinaryTree(TreeNode* root) {
if (!root) return 0;
queue<pair<TreeNode*, ULL>> q;
q.emplace(root, 0);
ULL ans = 0;
while (q.size()) {
ULL cnt = q.size(), minId, maxId;
for (int i = 0; i < cnt; ++i) {
auto p = q.front();
q.pop();
auto node = p.first;
ULL nodeId = p.second;
if (node->left) q.emplace(node->left, nodeId * 2);
if (node->right) q.emplace(node->right, nodeId * 2 + 1);
if (i == 0) minId = nodeId;
if (i == cnt - 1) maxId = nodeId;
}
ans = max(ans, maxId - minId + 1);
}
return ans;
}
};
Solution 3. Level-order Traversal
When there is only one node in this level, reset the id to be 0.
// OJ: https://leetcode.com/problems/maximum-width-of-binary-tree/
// Time: O(N)
// Space: O(N)
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
if (!root) return 0;
queue<pair<TreeNode*, int>> q;
q.emplace(root, 0);
int ans = 0;
while (q.size()) {
int cnt = q.size();
if (cnt == 1) {
q.emplace(q.front().first, 0);
q.pop();
}
ans = max(ans, q.back().second - q.front().second + 1);
while (cnt--) {
root = q.front().first;
int id = q.front().second;
q.pop();
if (root->left) q.emplace(root->left, 2 * id);
if (root->right) q.emplace(root->right, 2 * id + 1);
}
}
return ans;
}
};
-
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int widthOfBinaryTree(TreeNode root) { if (root == null) return 0; int maxWidth = 0; Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>(); Queue<Integer> numQueue = new LinkedList<Integer>(); nodeQueue.offer(root); numQueue.offer(0); while (!nodeQueue.isEmpty()) { int leftmost = -1, rightmost = -1; int size = nodeQueue.size(); for (int i = 0; i < size; i++) { TreeNode node = nodeQueue.poll(); int num = numQueue.poll(); if (leftmost < 0) leftmost = num; rightmost = num; TreeNode left = node.left, right = node.right; if (left != null) { nodeQueue.offer(left); numQueue.offer(num * 2 + 1); } if (right != null) { nodeQueue.offer(right); numQueue.offer(num * 2 + 2); } } int width = rightmost - leftmost + 1; maxWidth = Math.max(maxWidth, width); } return maxWidth; } } ############ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int widthOfBinaryTree(TreeNode root) { Deque<Pair<TreeNode, Integer>> q = new ArrayDeque<>(); q.offer(new Pair<>(root, 1)); int ans = 0; while (!q.isEmpty()) { ans = Math.max(ans, q.peekLast().getValue() - q.peekFirst().getValue() + 1); for (int n = q.size(); n > 0; --n) { var p = q.pollFirst(); root = p.getKey(); int i = p.getValue(); if (root.left != null) { q.offer(new Pair<>(root.left, i << 1)); } if (root.right != null) { q.offer(new Pair<>(root.right, i << 1 | 1)); } } } return ans; } } -
// OJ: https://leetcode.com/problems/maximum-width-of-binary-tree/ // Time: O(N) // Space: O(H) class Solution { typedef unsigned long long ULL; vector<vector<ULL>> v; ULL ans = 0; void dfs(TreeNode *node, int lv, ULL nodeId) { if (!node) return; if (v.size() <= lv) v.push_back({ULLONG_MAX, 0}); v[lv][0] = min(v[lv][0], nodeId); v[lv][1] = max(v[lv][1], nodeId); ans = max(ans, v[lv][1] - v[lv][0] + 1); dfs(node->left, lv + 1, 2 * nodeId); dfs(node->right, lv + 1, 2 * nodeId + 1); } public: int widthOfBinaryTree(TreeNode* root) { if (!root) return 0; dfs(root, 0, 0); return ans; } }; -
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int: ans = 0 q = deque([(root, 1)]) while q: ans = max(ans, q[-1][1] - q[0][1] + 1) for _ in range(len(q)): root, i = q.popleft() if root.left: q.append((root.left, i << 1)) if root.right: q.append((root.right, i << 1 | 1)) return ans ############ class Solution(object): def widthOfBinaryTree(self, root): """ :type root: TreeNode :rtype: int """ def dfs(root, x, y, num, dmin, dmax): if root: left = dfs(root.left, x - 1, y + 1, num * 2, dmin, dmax) right = dfs(root.right, x + 1, y + 1, 1 + num * 2, dmin, dmax) dmin[y] = min(num, dmin.get(y, float("inf"))) dmax[y] = max(num, dmax.get(y, float("-inf"))) return max(left or 0, right or 0, 1 + dmax[y] - dmin[y]) return dfs(root, 0, 0, 1, {}, {}) -
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func widthOfBinaryTree(root *TreeNode) int { q := []pair{ {root, 1} } ans := 0 for len(q) > 0 { ans = max(ans, q[len(q)-1].i-q[0].i+1) for n := len(q); n > 0; n-- { p := q[0] q = q[1:] root = p.node if root.Left != nil { q = append(q, pair{root.Left, p.i << 1}) } if root.Right != nil { q = append(q, pair{root.Right, p.i<<1 | 1}) } } } return ans } type pair struct { node *TreeNode i int } func max(a, b int) int { if a > b { return a } return b }