C++ में बाइनरी ट्री के पत्ते खोजें - स्तर दर स्तर संग्रह

समस्या विवरण

मान लीजिए हमारे पास एक बाइनरी ट्री है। हम सभी पत्तियों को संग्रहित और हटाएंगे और तब तक दोहराएंगे जब तक ट्री खाली न हो जाए।

उदाहरण के लिए, यदि इनपुट इस तरह का ट्री है:

तो आउटपुट [[4,5,3],[2],[1]] होगा।

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

DFS का उपयोग करके प्रत्येक नोड की ऊंचाई (पत्तियों से दूरी) की गणना करें:

1. एक मैप sz परिभाषित करें - नोड मान से ऊंचाई मैप करने के लिए
2. एक 2D सरणी ret परिभाषित करें - परिणाम संग्रहित करने के लिए
3. एक फ़ंक्शन dfs() परिभाषित करें जो नोड लेता है:
   • यदि नोड null है, तो 0 लौटाएं
   • sz[नोड का मान] := 1 + max(dfs(बाएं), dfs(दाएं))
   • यदि ret का आकार < sz[नोड का मान], तो एक खाली सरणी temp बनाएं और ret में जोड़ें
   • नोड के मान को ret[sz[नोड का मान] - 1] में जोड़ें
   • sz[नोड का मान] लौटाएं
4. मुख्य विधि से: dfs(root) कॉल करें और ret लौटाएं

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

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

void print_vector(vector<vector<auto> > v){ 
    cout << "["; 
    for(int i = 0; i<v.size(); i++){ 
        cout << "["; 
        for(int j = 0; j <v[i].size(); j++){ 
            cout << v[i][j] << ", "; 
        } 
        cout << "],"; 
    } 
    cout << "]"<<endl; 
} 

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: 
    unordered_map <int, int> sz; 
    vector < vector <int> > ret; 
    
    int dfs(TreeNode* node){ 
        if(!node) return 0; 
        sz[node->val] = 1 + max(dfs(node->left), dfs(node->right)); 
        if(ret.size() < sz[node->val]){ 
            vector <int> temp; 
            ret.push_back(temp); 
        } 
        ret[sz[node->val] - 1].push_back(node->val); 
        return sz[node->val]; 
    } 
    
    vector<vector<int>> findLeaves(TreeNode* root) { 
        dfs(root); 
        return ret; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<int> v = {1,2,3,4,5}; 
    TreeNode *root = make_tree(v); 
    print_vector(ob.findLeaves(root)); 
    return 0;
}

इनपुट

{1,2,3,4,5}

आउटपुट

[[3, 5, 4, ],[2, ],[1, ],]