C++ में बाइनरी ट्री को लिंक्ड लिस्ट में फ्लैट करना

मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें इसे स्थानांतरित (in-place) करके लिंक्ड लिस्ट में बदलना है (दायाँ पॉइंटर अगले नोड को इंगित करे, बायाँ पॉइंटर null हो)।

उदाहरण: ट्री [1,2,5,3,4] → फ्लैट लिस्ट: 1→2→3→4→5 (प्रीऑर्डर ट्रैवर्सल क्रम)।

रिवर्स प्रीऑर्डर ट्रैवर्सल

1. ग्लोबल prev = null रखें।
2. रिकर्सिव flatten(root):
   • यदि रूट null है, तो लौटें।
   • flatten(root->right) (पहले दायाँ)।
   • flatten(root->left) (फिर बायाँ)।
   • root->right = prev, root->left = NULL।
   • prev = root।

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* prev = NULL;
    void flatten(TreeNode* root) {
        if (!root) return;
        flatten(root->right);
        flatten(root->left);
        root->right = prev;
        root->left = NULL;
        prev = root;
    }
};

int main() {
    // ट्री बनाने और टेस्ट करने का कोड
    return 0;
}

इनपुट

[1,2,5,3,4]

आउटपुट

1, 2, 3, 4, 5,