ความกว้างสูงสุดของต้นไม้แบนารี (Maximum Width of Binary Tree) ใน C++

ความกว้างสูงสุดของต้นไม้แบนารี (Maximum Width of Binary Tree)

ความกว้างของระดับในต้นไม้แบนารี คือระยะห่างระหว่างโหนดซ้ายสุดและขวาสุดที่ไม่ใช่ null (นับโหนด null ระหว่างทางด้วย) ความกว้างของต้นไม้คือค่าสูงสุดของความกว้างทุกระดับ

ตัวอย่าง: ต้นไม้ [1,3,2,5,3,null,9] ความกว้างสูงสุดคือ 4 (ระดับสุดท้าย: [5,3,null,9])

ขั้นตอนการแก้ปัญหา (BFS + Indexing)

1. ใช้ deque เก็บคู่ (node, index) โดย index คำนวณแบบ heap: root=1, left=2*i, right=2*i+1
2. เริ่มจาก q.push({root, 1}), ans = 1
3. วนลูปในขณะที่คิวไม่ว่าง:
   • size = q.size()
   • ถ้า size == 1 ให้ reset index ของโหนดเดียวเป็น 1 (ป้องกัน overflow)
   • ประมวลผลทุกโหนดในระดับนี้:
     • นำโหนดออกจากคิว
     • ใส่ลูกซ้าย/ขวาพร้อม index ใหม่เข้าไป
   • หลังประมวลผลระดับเสร็จ: ถ้าคิวมี >1 โหนด ans = max(ans, q.back().second - q.front().second + 1)
4. คืนค่า ans

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) { val = data; left = NULL; right = NULL; }
};

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if (!root) return 0;
        deque<pair<TreeNode*, long long>> q;
        q.push_back({root, 1});
        int ans = 1;
        while (!q.empty()) {
            int sz = q.size();
            if (sz == 1) {
                q.front().second = 1; // reset index ป้องกัน overflow
            }
            while (sz--) {
                auto [node, idx] = q.front(); q.pop_front();
                if (node->left) q.push_back({node->left, idx * 2});
                if (node->right) q.push_back({node->right, idx * 2 + 1});
            }
            if (q.size() > 1) {
                ans = max(ans, (int)(q.back().second - q.front().second + 1));
            }
        }
        return ans;
    }
};

อินพุทและเอาต์พุทตัวอย่าง

Input: [1,3,2,5,3,null,9]

Output: 4