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

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

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

उदाहरण: [3,2,1,6,0,5] के लिए अधिकतम ट्री बनेगा (चित्र देखें)।

रिकर्सिव विभाजन और विजय

1. solve(nums, left, right) फंक्शन परिभाषित करें।
2. यदि left > right, तो null लौटाएँ।
3. maxIndex और maxVal को left..right में अधिकतम तत्व का इंडेक्स और मान खोजें।
4. नोड बनाएँ जिसका मान maxVal हो।
5. node->left = solve(nums, left, maxIndex-1)।
6. node->right = solve(nums, maxIndex+1, right)।
7. node लौटाएँ।
8. मुख्य फंक्शन से solve(nums, 0, n-1) कॉल करें।

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:
    TreeNode* solve(vector<int>& nums, int left, int right) {
        if (left > right) return NULL;
        int maxIdx = left;
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] > nums[maxIdx]) maxIdx = i;
        }
        TreeNode* node = new TreeNode(nums[maxIdx]);
        node->left = solve(nums, left, maxIdx - 1);
        node->right = solve(nums, maxIdx + 1, right);
        return node;
    }
    
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return solve(nums, 0, nums.size() - 1);
    }
};

// इनऑर्डर ट्रैवर्सल प्रिंट
void inorder(TreeNode* root) {
    if (root) {
        inorder(root->left);
        cout << root->val << " ";
        inorder(root->right);
    }
}

int main() {
    vector<int> v = {3,2,1,6,0,5};
    Solution ob;
    TreeNode* root = ob.constructMaximumBinaryTree(v);
    inorder(root); // 3 2 1 6 0 5 (इनऑर्डर)
    return 0;
}

इनपुट

[3,2,1,6,0,5]

आउटपुट

4 3 2 7 1 6