二叉树最大宽度

Leetcode题目链接

描述

详见中文题目链接。

解答

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if (!root) return 0;
        size_t res = 1;
        queue<pair<TreeNode*, size_t>> que;
        que.push({root, 1LL});

        while (!que.empty()) {
            size_t len = que.size();
            size_t start = que.front().second;
            size_t end = que.back().second;
            res = max(res, end - start + 1);

            while (len--) {
                auto [node, index] = que.front();
                que.pop();

                if (node->left) {
                    que.push({node->left, index * 2});
                }
                if (node->right) {
                    que.push({node->right, index * 2 + 1LL});
                }
            }
        }

        return res;
    }
};