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

C++ में बाइनरी ट्री का बॉटम लेफ्ट मान


मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें ट्री की अंतिम पंक्ति (सबसे गहरे लेवल) का सबसे बायाँ मान ढूंढना है।

उदाहरण: ट्री [3,5,1,6,2,0,8,null,null,7,4] के लिए अंतिम पंक्ति [7,4] है, इसलिए बॉटम लेफ्ट मान 7 है।

DFS + गहराई ट्रैकिंग

  1. दो वेरिएबल्स ans और maxLevel (प्रारंभ में -1) रखें।
  2. रिकर्सिव solve(node, level):
    • यदि node null है, तो लौटें।
    • यदि level > maxLevel, तो ans = node->val, maxLevel = level।
    • पहले solve(node->left, level+1) कॉल करें (बाएँ पहले ताकि बायाँ मान पहले मिले)।
    • फिर solve(node->right, level+1) कॉल करें।
  3. मुख्य फंक्शन से solve(root, 0) कॉल करें और ans लौटाएँ।

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

class Solution {
public:
    int ans = 0;
    int maxLevel = -1;
    void solve(TreeNode* node, int level = 0) {
        if (!node) return;
        if (level > maxLevel) {
            ans = node->val;
            maxLevel = level;
        }
        solve(node->left, level + 1);
        solve(node->right, level + 1);
    }
    int findBottomLeftValue(TreeNode* root) {
        maxLevel = -1;
        solve(root);
        return ans;
    }
};

int main() {
    // ट्री बनाने का कोड
    Solution ob;
    // cout << ob.findBottomLeftValue(root);
    return 0;
}

इनपुट

[3,5,1,6,2,0,8,null,null,7,4]

आउटपुट

7
  1. C++ में अधिकतम बाइनरी ट्री निर्माण C++ में अधिकतम बाइनरी ट्री निर्माण

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

  1. C++ में प्रत्येक ट्री पंक्ति का सबसे बड़ा मान C++ में प्रत्येक ट्री पंक्ति का सबसे बड़ा मान

    मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें ट्री के प्रत्येक लेवल का सबसे बड़ा तत्व ढूंढना है। उदाहरण: ट्री [1,3,2,5,3,null,9] के लिए आउटपुट [1,3,9] होगा (लेवल 0: 1, लेवल 1: max(3,2)=3, लेवल 2: max(5,3,9)=9)। DFS + लेवल ट्रैकिंग एक सरणी ans बनाएँ जहाँ ans[level] उस लेवल का अधिकतम मान स्टोर करे।

  1. C++ में बाइनरी सर्च ट्री में न्यूनतम मान वाला नोड ज्ञात करें C++ में बाइनरी सर्च ट्री में न्यूनतम मान वाला नोड ज्ञात करें

    मान लीजिए हमारे पास एक बाइनरी सर्च ट्री है। हमें बाइनरी सर्च ट्री में न्यूनतम तत्व ढूंढना है। इसलिए यदि BST नीचे की तरह है: न्यूनतम तत्व 1 होगा। जैसा कि हम जानते हैं कि बायां उपट्री हमेशा छोटे तत्वों को धारण करता है। इसलिए यदि हम बाएं उपट्री के माध्यम से तब तक ट्रैवर्स करते हैं जब तक बायां NULL नही