34. 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 are also counted into the length calculation.
It is guaranteed that the answer will in the range of 32-bit signed integer.
Example 1:
Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).
Example 2:
Input: root = [1,3,null,5,3]
Output: 2
Explanation: The maximum width existing in the third level with the length 2 (5,3).
Example 3:
Input: root = [1,3,2,5]
Output: 2
Explanation: The maximum width existing in the second level with the length 2 (3,2).
Example 4:
Input: root = [1,3,2,5,null,null,9,6,null,null,7]
Output: 8
Explanation: The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).
Solution:
Approach: Left Child at pos = 2*i +1 Right Child at pos = 2*i + 2 Finding the distance between the 1st left and last right of a level
class Solution
{
public:
int widthOfBinaryTree(TreeNode *root)
{
if (root == NULL)
{
return 0;
}
queue<TreeNode *> q;
queue<int> idx;
int maxWidth = 0;
q.push(root);
idx.push(0);
while (!q.empty())
{
int s = q.size();
int i = 0;
int start = 0;
int end = 0;
int minVal = idx.front();
while (i < s)
{
int pos = idx.front() - minVal;
idx.pop();
if (i == 0)
{
start = pos - minVal;
}
if (i == s - 1)
{
end = pos - minVal;
}
TreeNode *t = q.front();
q.pop();
if (t->left)
{
q.push(t->left);
idx.push(2 * pos + 1);
}
if (t->right)
{
q.push(t->right);
idx.push(2 * pos + 2);
}
i++;
}
maxWidth = max(maxWidth, (end - start) + 1);
}
return maxWidth;
}
};
Last updated
Was this helpful?