C++ में बाइनरी ट्री की अधिकतम चौड़ाई

मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें ट्री की अधिकतम चौड़ाई ढूंढनी है। एक लेवल की चौड़ाई उस लेवल के सबसे बाएँ और सबसे दाएँ नॉन-नल नोड्स के बीच की दूरी है (बीच के नल नोड्स भी गिने जाते हैं)।

उदाहरण: ट्री [1,3,2,5,3,null,9] के लिए अधिकतम चौड़ाई 4 है (अंतिम लेवल [5,3,null,9] की लंबाई 4)।

BFS + इंडेक्सिंग

1. एक डबल-एंडेड क्यू q में (node, index) जोड़े स्टोर करें। रूट का इंडेक्स 1।
2. बाएँ चाइल्ड का इंडेक्स = 2*parent_index, दाएँ का = 2*parent_index + 1।
3. प्रत्येक लेवल के लिए, चौड़ाई = last_index - first_index + 1।
4. सभी लेवल्स की अधिकतम चौड़ाई ट्रैक करें।

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();
            long long first = q.front().second;
            long long last = q.back().second;
            ans = max(ans, int(last - first + 1));
            
            while (sz--) {
                auto [node, idx] = q.front(); q.pop_front();
                if (node->left) q.push_back({node->left, 2 * idx});
                if (node->right) q.push_back({node->right, 2 * idx + 1});
            }
        }
        return ans;
    }
};

int main() {
    // ट्री बनाने का कोड
    Solution ob;
    // cout << ob.widthOfBinaryTree(root);
    return 0;
}

इनपुट

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

आउटपुट

4