662. Maximum Width of Binary Tree
1. Description
Given a binary tree, write a function to get 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 right most non-null nodes in the level, 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.
2. Example
Example 1:
Input: [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).
3. Constraints
- The given binary tree will have between 1 and 3000 nodes.
4. Solutions
My Accepted Solution
n is the number of nodes in m_root
Time complexity: O(n)
Space complexity: O(n)
// breadth-first search, it could also use depth-first search
class Solution
{
public:
// int widthOfBinaryTree(TreeNode* root)
int widthOfBinaryTree(TreeNode *m_root)
{
if(!m_root) return 0;
m_root->val = 1;
queue<TreeNode *> currentLevelNodes{{m_root}};
queue<TreeNode *> nextLevelNodes;
int maxWidth = 1;
while(!currentLevelNodes.empty() || !nextLevelNodes.empty())
{
if(currentLevelNodes.empty())
{
// if every level only has one node, its position will be very big soon
// we only need the width of nodes, and we actually don't care their real position
// so we set a excursion, and let every nodes minus it to keep their position small
auto firstNode = nextLevelNodes.front();
nextLevelNodes.pop();
int excursion = firstNode->val - 1;
firstNode->val = 1;
currentLevelNodes.push(firstNode);
while(!nextLevelNodes.empty())
{
auto node = nextLevelNodes.front();
nextLevelNodes.pop();
node->val -= excursion;
maxWidth = max(maxWidth, node->val);
currentLevelNodes.push(node);
}
}
else
{
auto node = currentLevelNodes.front();
currentLevelNodes.pop();
if(node->left)
{
node->left->val = (node->val << 1);
nextLevelNodes.push(node->left);
}
if(node->right)
{
node->right->val = ((node->val << 1) + 1);
nextLevelNodes.push(node->right);
}
}
}
return maxWidth;
}
};