C++ में बाइनरी ट्री वर्टिकल ऑर्डर ट्रैवर्सल - स्तंभवार नोड मान

समस्या विवरण

मान लीजिए एक बाइनरी ट्री है, हमें उसके नोड्स के मान का वर्टिकल ऑर्डर ट्रैवर्सल ढूंढना है। यदि दो नोड्स एक ही पंक्ति और स्तंभ में हैं, तो क्रम बाएं से दाएं होना चाहिए।

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

तो आउटपुट [[9],[3,15],[20],[7]] होगा।

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

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

1. एक मैप m परिभाषित करें - स्तंभ सूचकांक को नोड मानों की सूची पर मैप करने के लिए
2. solve() फ़ंक्शन परिभाषित करें जो नोड, x (स्तंभ) लेता है:
   • यदि नोड null है, तो लौटें
   • solve(बाएं, x-1)
   • solve(दाएं, x+1)
   • नोड के मान को m[x] में जोड़ें
3. मुख्य विधि से:
   • यदि रूट null है, तो खाली सरणी लौटाएं
   • एक कतार q परिभाषित करें, {0, रूट} डालें
   • रूट के मान को m[0] में जोड़ें
   • जब q खाली न हो:
     • sz := q का आकार
     • sz बार लूप करें:
       • curr := q का पहला तत्व, q से हटाएं
       • नोड = curr का दूसरा तत्व, x = curr का पहला तत्व
       • यदि बायां बच्चा मौजूद है: {x-1, बायां} को q में डालें, मान को m[x-1] में जोड़ें
       • यदि दायां बच्चा मौजूद है: {x+1, दायां} को q में डालें, मान को m[x+1] में जोड़ें
   • एक 2D सरणी ret परिभाषित करें
   • m के प्रत्येक कुंजी-मान जोड़े के लिए मान को ret में जोड़ें
   • 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: 
    map<int, vector<int>> m; 
    
    void solve(TreeNode* node, int x = 0){ 
        if (!node || node->val == 0) 
            return; 
        solve(node->left, x - 1); 
        solve(node->right, x + 1); 
        m[x].push_back(node->val); 
    } 
    
    static bool cmp(vector<int>& a, vector<int>& b){ 
        return a[0] != b[0] ? a[0] < b[0] : a[1] < b[1]; 
    } 
    
    vector<vector<int>> verticalOrder(TreeNode* root){ 
        if (!root) 
            return {}; 
        queue<pair<int, TreeNode*>> q; 
        q.push({ 0, root }); 
        m[0].push_back(root->val); 
        while (!q.empty()) { 
            int sz = q.size(); 
            while (sz--) { 
                pair<int, TreeNode*> curr = q.front(); 
                q.pop(); 
                TreeNode* node = curr.second; 
                int x = curr.first; 
                if (node->left && node->left->val != 0) { 
                    q.push({ x - 1, node->left }); 
                    m[x - 1].push_back(node->left->val); 
                } 
                if (node->right && node->right->val != 0) { 
                    q.push({ x + 1, node->right }); 
                    m[x + 1].push_back(node->right->val); 
                } 
            } 
        } 
        vector<vector<int>> ret; 
        map<int, vector<int>>::iterator it = m.begin(); 
        while (it != m.end()) { 
            ret.push_back(it->second); 
            it++; 
        } 
        return ret; 
    } 
}; 

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

इनपुट

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

आउटपुट

[[9, ],[3, 15, ],[20, ],[7, ],]