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

C++ में बाइनरी ट्री का लेफ्ट साइड व्यू खोजें


बाइनरी ट्री को बाएं से देखने पर जो नोड्स दिखाई देते हैं, उन्हें लेफ्ट साइड व्यू कहते हैं। उदाहरण ट्री के लिए आउटपुट [1, 2, 5] है।

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

हम प्री-ऑर्डर DFS का उपयोग करते हैं जहां हम पहले बाएं सबट्री को एक्सप्लोर करते हैं:

  1. एक सरणी ret और वेरिएबल lvl = -1 रखें।
  2. dfs(node, level) फंक्शन:
    • यदि नोड नल है, तो वापस लौटें।
    • यदि level > lvl, तो lvl = level और नोड का मान ret में जोड़ें।
    • पहले बाएं, फिर दाएं बच्चे पर पुनरावृति करें (level + 1 के साथ)।
  3. मुख्य फंक्शन से dfs(root, 0) कॉल करें और ret वापस करें।

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

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

void print_vector(vector 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 = right = NULL;
    }
};

class Solution {
public:
    vector ret;
    int lvl;
    void dfs(TreeNode* node, int c = 1) {
        if (!node) return;
        if (c > lvl) {
            lvl = c;
            ret.push_back(node->val);
        }
        dfs(node->left, c + 1);
        dfs(node->right, c + 1);
    }
    vector solve(TreeNode* root) {
        lvl = -1;
        dfs(root, 0);
        return ret;
    }
};

int main() {
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(4);
    Solution ob;
    print_vector(ob.solve(root));
    return 0;
}

इनपुट

TreeNode *root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->right = new TreeNode(5); root->right->right = new TreeNode(4);

आउटपुट

[1,2,5]
  1. C++ में अधिकतम बाइनरी ट्री निर्माण C++ में अधिकतम बाइनरी ट्री निर्माण

    मान लीजिए हमारे पास एक पूर्णांक सरणी है जिसके सभी तत्व अद्वितीय हैं। एक अधिकतम बाइनरी ट्री निम्न नियमों से बनता है: रूट सरणी का अधिकतम तत्व होता है। बायाँ सबट्री अधिकतम तत्व के बाएँ भाग से बने सबसरणी का अधिकतम ट्री होता है। दायाँ सबट्री अधिकतम तत्व के दाएँ भाग से बने सबसरणी का अधिकतम ट्री होता है।

  1. C++ में बाइनरी ट्री का राइट साइड व्यू C++ में बाइनरी ट्री का राइट साइड व्यू

    मान लीजिए हमारे पास एक बाइनरी ट्री है, यदि हम ट्री को दाईं ओर से देखते हैं, तो हम इसके कुछ एलिमेंट्स देख सकते हैं। हमें उन एलिमेंट्स को प्रदर्शित करना होगा। तो यदि ट्री इस तरह है −इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −हम dfs के लिए एक हेल्पिंग मेथड बनाएंगे। यह tree_node, उत्तरो

  1. C++ में बाइनरी ट्री में निकटतम लीफ ढूंढें C++ में बाइनरी ट्री में निकटतम लीफ ढूंढें

    मान लीजिए, एक बाइनरी ट्री दिया गया है। इसमें अलग-अलग लेवल पर लीफ नोड्स हैं। एक और पॉइंटर दिया गया है, जो एक नोड को इंगित कर रहा है। हमें इंगित नोड से निकटतम लीफ नोड की दूरी ढूंढनी है। ट्री को नीचे जैसा मानें - यहां लीफ नोड्स 2, -2 और 6 हैं। यदि पॉइंटर नोड -5 पर इंगित कर रहा है, तो -5 से निकटतम नोड