662. Maximum Width of Binary Tree

662. Maximum Width of Binary Tree

題意

• 此題目要求我們找出給定二元樹的最大寬度

  • 二元樹的寬度定義為某層中最左邊和最右邊的非空節點間的節點數量（包含最左和最右的節點）

  • 若某層只有一個節點，則該層的寬度為1

限制

• The number of nodes in the tree is in the range [1, 3000].

• -100 <= Node.val <= 100

思考

• 通過使用 BFS

  • 逐層遍歷樹，同時維護每個節點的位置索引，從而計算出每一層的寬度

  • 將每個節點的位置標記為從1開始的索引，並利用二進制位操作來確定每個子節點的位置

    • left child 的位置是 parent 位置的兩倍（即 num << 1）

    • right child 的位置是 parent 位置的兩倍再加一（即 (num << 1) | 1）

實作流程

1. 如果 root 不存在，直接返回寬度為 0

2. 使用一個 queue 來儲存每個節點及其索引，初始將 root 及其索引1放入隊列

3. 遍歷 queue，對於 queue 中的每個節點，更新當前層的寬度，比較並保持最大寬度

   1. q.back() - q.front()

4. 將 non-null 的 child 及其計算後的索引 push 到 queue

5. 遍歷結束後，返回記錄的最大寬度

Solution

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

        int ans = 1;
        queue<pair<TreeNode*, unsigned>> q;
        q.push({ root, 1 });

        while (!q.empty()) {
            int n = q.size();

            ans = max(ans, (int)(q.back().second - q.front().second + 1));

            while (n--) {
                auto [node, num] = q.front();
                q.pop();
                if (node->left) {
                    q.push({ node->left, num << 1 });
                }
                if (node->right) {
                    q.push({ node->right, (num << 1) | 1 });
                }
            }
        }
        return ans;
    }
};