662. Maximum Width of Binary Tree

2020, Dec 18 2 mins read

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

Breadth-First Search

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;
    }
};