C++ में बाइनरी ट्री के उस स्तर को खोजें जिसका योग न्यूनतम है

एक बाइनरी ट्री दिया गया है जहां रूट का स्तर 1 है। हमें वह सबसे छोटा स्तर X ढूंढना है जहां सभी नोड्स के मानों का योग न्यूनतम हो।

उदाहरण ट्री में रूट 5 है, बाएं 4, दाएं -10, आदि। स्तर 2 का योग 4 + (-10) = -6 है, जो न्यूनतम है, इसलिए आउटपुट 2 है।

समाधान दृष्टिकोण

हम लेवल ऑर्डर ट्रैवर्सल (BFS) का उपयोग करते हैं:

1. क्यू में रूट डालें। level = 1, sum = root->val, ansLevel = 1, ansSum = sum।
2. जब तक क्यू खाली नहीं:
   • वर्तमान स्तर के नोड्स की संख्या (capacity) लें।
   • level++, sum = 0।
   • प्रत्येक नोड के लिए: उसके बच्चों को क्यू में डालें और उनके मान sum में जोड़ें।
   • स्तर समाप्त होने पर, यदि sum < ansSum, तो ansSum और ansLevel अपडेट करें।
3. ansLevel वापस करें।

C++ कार्यान्वयन

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

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

class Solution {
public:
    int solve(TreeNode* r) {
        int level = 1, sum = r->val;
        int ansLevel = level, ansSum = sum;
        queue q;
        q.push(r);
        while (!q.empty()) {
            int capacity = q.size();
            level++;
            sum = 0;
            while (capacity--) {
                TreeNode* node = q.front(); q.pop();
                if (node->right) {
                    sum += node->right->val;
                    q.push(node->right);
                }
                if (node->left) {
                    sum += node->left->val;
                    q.push(node->left);
                }
            }
            if (ansSum > sum) {
                ansSum = sum;
                ansLevel = level;
            }
        }
        return ansLevel;
    }
};

int main() {
    TreeNode *root = new TreeNode(5);
    root->left = new TreeNode(4);
    root->right = new TreeNode(-10);
    root->left->right = new TreeNode(-2);
    root->right->left = new TreeNode(-7);
    root->right->right = new TreeNode(15);
    Solution ob;
    cout << ob.solve(root);
    return 0;
}

इनपुट

TreeNode *root = new TreeNode(5); root->left = new TreeNode(4); root->right = new TreeNode(-10); root->left->right = new TreeNode(-2); root->right->left = new TreeNode(-7); root->right->right = new TreeNode(15);

आउटपुट

2