C++ में बाइनरी ट्री प्रूनिंग

मान लीजिए हमारे पास एक बाइनरी ट्री का हेड नोड root है, जहाँ प्रत्येक नोड का मान या तो 0 या 1 है। हमें वही ट्री लौटाना है जहाँ हर वह सबट्री हटा दी गई हो जिसमें 1 नहीं है।

उदाहरण: इनपुट ट्री [1,1,0,1,1,0,1,0] के लिए, आउटपुट ट्री में केवल वही नोड्स रहेंगे जिनके सबट्री में कम से कम एक 1 है।

पोस्ट-ऑर्डर रिकर्सन

1. रिकर्सिव मेथड pruneTree(node) परिभाषित करें।
2. यदि node null है, तो null लौटाएँ।
3. node->left = pruneTree(node->left)।
4. node->right = pruneTree(node->right)।
5. यदि node->left == null && node->right == null && node->val == 0, तो null लौटाएँ।
6. अन्यथा node लौटाएँ।

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* pruneTree(TreeNode* node) {
        if (!node) return NULL;
        node->left = pruneTree(node->left);
        node->right = pruneTree(node->right);
        if (!node->left && !node->right && !node->val) {
            return NULL;
        }
        return node;
    }
};

// टेस्ट के लिए लेवल ऑर्डर ट्रैवर्सल प्रिंट
void printTree(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);
    cout << "[";
    while (!q.empty()) {
        TreeNode* curr = q.front(); q.pop();
        if (curr) {
            cout << curr->val << ", ";
            q.push(curr->left);
            q.push(curr->right);
        } else {
            cout << "null, ";
        }
    }
    cout << "]" << endl;
}

int main() {
    // ट्री बनाने का कोड
    Solution ob;
    // TreeNode* root = make_tree(...);
    // printTree(ob.pruneTree(root));
    return 0;
}

इनपुट

[1,1,0,1,1,0,1,0]

आउटपुट

[1, 1, 0, 1, 1, 1, ]