C++ में बाइनरी सर्च ट्री को सिंगली लिंक्ड लिस्ट में बदलना

मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें इसे इन-प्लेस (in-place) एक सिंगली लिंक्ड लिस्ट में बदलना है।

उदाहरण के लिए, दिए गए ट्री के लिए आउटपुट एक सॉर्टेड लिंक्ड लिस्ट होगी।

समाधान दृष्टिकोण (रिवर्स इनऑर्डर ट्रैवर्सल)

• prev := NULL सेट करें।
• एक रिकर्सिव फ़ंक्शन solve() परिभाषित करें जो रूट लेता है।
• यदि रूट NULL है, तो वापस लौटें।
• solve(root->right) कॉल करें (पहले राइट सबट्री)।
• solve(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() { 
    // ट्री निर्माण कोड... 
    Solution ob; 
    ob.flatten(root); 
    // लिंक्ड लिस्ट प्रिंट करें 
    return 0; 
}

इनपुट

{1,2,5,3,4}

आउटपुट

1, 2, 3, 4, 5,