C++ में बाइनरी ट्री की न्यूनतम गहराई

समस्या विवरण

मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें उस ट्री की न्यूनतम गहराई ज्ञात करनी है। जैसा कि हम जानते हैं, न्यूनतम गहराई रूट नोड से निकटतम लीफ नोड तक के सबसे छोटे पथ पर नोड्स की संख्या है।

उदाहरण

यदि इनपुट ट्री है:

तो आउटपुट होगा 2

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए निम्नलिखित चरणों का पालन करें (लेवल ऑर्डर ट्रैवर्सल / BFS):

ट्री नोड्स की एक सरणी aa परिभाषित करें
aa के अंत में रूट डालें
ट्री नोड्स की एक और सरणी ak परिभाषित करें
level := 0
यदि रूट null है, तो 0 लौटाएं
जब aa का आकार 0 के बराबर नहीं है:
- सरणी ak को क्लियर करें
- level को 1 से बढ़ाएं
- aa में प्रत्येक नोड a के लिए:
  - यदि (a का लेफ्ट null है) और (a का राइट null है):
    - level लौटाएं
    - लूप से बाहर निकलें
  - यदि a का लेफ्ट null नहीं है:
    - a के लेफ्ट को ak के अंत में डालें
  - यदि a का राइट null नहीं है:
    - a के राइट को ak के अंत में डालें
- aa := ak
0 लौटाएं

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

void insert(TreeNode **root, int val) {
    queue<TreeNode*> q;
    q.push(*root);
    while(q.size()) {
        TreeNode *temp = q.front();
        q.pop();
        if(!temp->left) {
            if(val != NULL)
                temp->left = new TreeNode(val);
            else
                temp->left = new TreeNode(0);
            return;
        } else {
            q.push(temp->left);
        }
        if(!temp->right) {
            if(val != NULL)
                temp->right = new TreeNode(val);
            else
                temp->right = new TreeNode(0);
            return;
        } else {
            q.push(temp->right);
        }
    }
}

TreeNode *make_tree(vector<int> v) {
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i < v.size(); i++) {
        insert(&root, v[i]);
    }
    return root;
}

class Solution {
public:
    int minDepth(TreeNode* root) {
        vector<TreeNode*> aa;
        aa.push_back(root);
        vector<TreeNode*> ak;
        int level = 0;
        if (root == NULL || root->val == 0) {
            return 0;
        }
        while (aa.size() != 0) {
            ak.clear();
            level++;
            for (TreeNode* a : aa) {
                if ((a->left == NULL || a->left->val == 0) && (a->right == NULL || a->right->val == 0)) {
                    return level;
                    break;
                }
                if (a->left != NULL) {
                    ak.push_back(a->left);
                }
                if (a->right != NULL) {
                    ak.push_back(a->right);
                }
            }
            aa = ak;
        }
        return 0;
    }
};

int main() {
    Solution ob;
    vector<int> v = {3,9,20,NULL,NULL,15,7};
    TreeNode *root = make_tree(v);
    cout << (ob.minDepth(root));
    return 0;
}

इनपुट

{3,9,20,NULL,NULL,15,7}