Leetcode 662 Solution

This article provides solution to leetcode question 662 (maximum-width-of-binary-tree)
Categories:
Tags:
Access this page by simply typing in "lcs 662" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/maximum-width-of-binary-tree

Solution

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if (root == NULL)
            return 0;

        queue<pair<TreeNode*, int>> q;
        q.push(make_pair(root, 0));

        int res = 0;
        while (!q.empty())
        {
            int l = q.front().second;
            int r = 0;

            int s = q.size();

            if (s == 1)
                q.front().second = 0;

            for (int i = 0; i < s; i++)
            {
                auto p = q.front();
                q.pop();

                auto node = p.first;
                r = p.second;

                if (node->left)
                    q.push(make_pair(node->left, 2 * r + 1));

                if (node->right)
                    q.push(make_pair(node->right, 2 * r + 2));
            }

            res = max(r - l + 1, res);
        }

        return res;
    }
};