Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में बाइनरी ट्री में सभी नोड्स दूरी K पर


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

उदाहरण के लिए, यदि इनपुट root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2 है, तो आउटपुट [7,4,1] होगा, क्योंकि लक्ष्य नोड से दूरी 2 पर नोड्स के मान 7, 4, और 1 हैं।

हल करने की विधि

हम निम्न चरणों का पालन करेंगे:

  • dfs() फ़ंक्शन परिभाषित करें जो प्रत्येक नोड के माता-पिता को मैप में संग्रहीत करता है।
  • मुख्य विधि में:
    • उत्तर सरणी ans परिभाषित करें।
    • dfs(root) कॉल करके माता-पिता मैप भरें।
    • (नोड, स्तर) युग्म के लिए एक कतार q परिभाषित करें।
    • {target, 0} को q में डालें।
    • देखे गए नोड्स के लिए एक सेट visited परिभाषित करें, target डालें।
    • जब तक q खाली न हो:
      • सामने का तत्व निकालें।
      • यदि स्तर == K, तो नोड का मान ans में जोड़ें।
      • बाएं, दाएं, और माता-पिता नोड्स को यदि वैध और अनदेखे हैं, तो स्तर+1 के साथ q में डालें।
    • ans लौटाएं।

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

#include <bits/stdc++.h> using namespace std; void print_vector(vector<int> v){    cout << "[";    for(int i = 0; i<v.size(); i++){       cout << v[i] << ", ";    }    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 <TreeNode*, TreeNode*> parent;    void dfs(TreeNode* node, TreeNode* pa = NULL){       if (!node)          return;       parent[node] = pa;       dfs(node->left, node);       dfs(node->right, node);    }    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {       vector<int> ans;       parent.clear();       dfs(root);       queue<pair<TreeNode*, int> > q;       q.push({ target, 0 });       set<TreeNode*> visited;       visited.insert(target);       while (!q.empty()) {          pair<TreeNode*, int> temp = q.front();          q.pop();          int level = temp.second;          TreeNode* node = temp.first;          if (level == k) {             ans.push_back(node->val);          }          if ((node->left && node->left->val != 0) && level + 1 <= k && !visited.count(node->left)) {             q.push({ node->left, level + 1 });             visited.insert(node->left);          }          if ((node->right && node->right->val != 0) && level + 1 <= k && !visited.count(node->right)){             q.push({ node->right, level + 1 });             visited.insert(node->right);          }          if (parent[node] != NULL && level + 1 <= k && !visited.count(parent[node])) {             q.push({ parent[node], level + 1 });             visited.insert(parent[node]);          }       }       return ans;    } }; main(){    Solution ob;    vector<int> v = {3,5,1,6,2,0,8,NULL,NULL,7,4};    TreeNode *root = make_tree(v);    TreeNode *target = root->left;    print_vector(ob.distanceK(root, target, 2)); }

इनपुट

{3,5,1,6,2,0,8,NULL,NULL,7,4}

आउटपुट

[7, 4, 1, ]

  1. C++ में बाइनरी सर्च ट्री के सभी विषम नोड्स प्रिंट करना C++ में बाइनरी सर्च ट्री के सभी विषम नोड्स प्रिंट करना

    इस समस्या में, हमें एक बाइनरी सर्च ट्री दी गई है और हमें उन सभी नोड्स को प्रिंट करना है जिनके मान विषम हैं। बाइनरी सर्च ट्री बाइनरी सर्च ट्री एक विशेष प्रकार का ट्री है जिसमें निम्नलिखित गुण होते हैं: बायां सबट्री हमेशा रूट नोड से छोटे मान रखता है। दायां सबट्री हमेशा रूट नोड से बड़े मान रखता है।

  1. बाइनरी ट्री में रूट से दिए गए नोड तक की दूरी खोजें C++ में बाइनरी ट्री में रूट से दिए गए नोड तक की दूरी खोजें C++ में

    मान लीजिए हमारे पास कुछ नोड्स के साथ एक बाइनरी ट्री है। हमें रूट और दूसरे नोड u के बीच की दूरी खोजनी है। मान लीजिए ट्री नीचे जैसा है: अब (रूट, 6) के बीच की दूरी = 2, पथ की लंबाई 2 है, (रूट, 8) के बीच की दूरी = 3 आदि। इस समस्या को हल करने के लिए, हम नोड को बाएं और दाएं सबट्री में खोजने के लिए एक पुन

  1. बाइनरी ट्री के दो नोड्स के बीच की दूरी खोजें C++ में बाइनरी ट्री के दो नोड्स के बीच की दूरी खोजें C++ में

    मान लीजिए हमारे पास कुछ नोड्स के साथ एक बाइनरी ट्री है। हमें दो नोड्स u और v के बीच की दूरी खोजनी है। मान लीजिए ट्री नीचे जैसा है - अब (4, 6) के बीच की दूरी = 4, पथ की लंबाई 4 है, (5, 8) के बीच की लंबाई = 5 आदि। इस समस्या को हल करने के लिए, हम LCA (निम्नतम सामान्य पूर्वज) खोजेंगे, फिर LCA से दो नोड