सी ++ लंबाई के रूट से लीफ पथ पर नोड्स को हटा दें

एक पेड़ को देखते हुए, और हमें दिए गए k से कम लंबाई वाले पथ के लीफ नोड को हटाने की जरूरत है, उदाहरण के लिए।

इनपुट -

K = 4.

आउटपुट -

स्पष्टीकरण

The paths were :
1. A -> B -> C -> E length = 4
2. A -> B -> C -> F length = 4
3. A -> B -> D length = 3
4. A -> G -> H length = 3
5. A -> B -> I length = 3
Now as you can see paths 3, 4, 5 have length of 3 which is less than given k so we remove the leaf nodes of these paths i.e. D, H, I.
Now for path 4 and 5 when H and I are removed we notice that now G is also a leaf node with path length 2 so we again remove node G and here our program ends.

हम पेड़ को पोस्ट-ऑर्डर प्रारूप में पार करेंगे; फिर, हम एक पुनरावर्ती फ़ंक्शन बनाते हैं जो हमारे लीफ नोड्स को हटा देता है यदि उनकी पथ लंबाई K से कम है।

समाधान खोजने के लिए दृष्टिकोण

इस दृष्टिकोण में, हम अब पोस्ट-ऑर्डर ट्रैवर्सल में ट्रैवर्स करते हैं; हम उन लीफ नोड्स को पुनरावर्ती रूप से हटाने का प्रयास करते हैं जिनकी पथ लंबाई k से कम होती है और इस तरह जारी रहती है।

उदाहरण

उपरोक्त दृष्टिकोण के लिए C++ कोड

#include<bits/stdc++.h>
using namespace std;
struct Node{ // structure of our node
    char data;
    Node *left, *right;
};
Node *newNode(int data){ // inserting new node
    Node *node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
Node *trimmer(Node *root, int len, int k){
    if (!root) // if root == NULL then we return
        return NULL;
    root -> left = trimmer(root -> left, len + 1, k); // traversing the left phase
    root -> right = trimmer(root -> right, len + 1, k); // traversing the right phase
    if (!root -> left && !root -> right && len < k){
        delete root;
        return NULL;
    }
    return root;
}
Node *trim(Node *root, int k){
    return trimmer(root, 1, k);
}
void printInorder(Node *root){
    if (root){
        printInorder(root->left);
        cout << root->data << " ";
        printInorder(root->right);
    }
}
int main(){
    int k = 4;
    Node *root = newNode('A');
    root->left = newNode('B');
    root->right = newNode('G');
    root->left->left = newNode('C');
    root->left->right = newNode('D');
    root->left->left->left = newNode('E');
    root->left->left->right = newNode('F');
    root->right->left = newNode('H');
    root->right->right = newNode('I');
    printInorder(root);
    cout << "\n";
    root = trim(root, k);
    printInorder(root);
    return 0;
}

आउटपुट

E C F B D A H G I
E C F B A

उपरोक्त कोड की व्याख्या

इस कोड में, हम एक रिकर्सिव फ़ंक्शन का उपयोग कर रहे हैं जो हमारे पेड़ को पार कर रहा है और बाएं और दाएं उपट्री के आंकड़े रख रहा है। अब हम एक लीफ नोड पर पहुंचते हैं; हम उस नोड तक पथ की लंबाई की जांच करते हैं। यदि पथ की लंबाई कम है, तो हम इस नोड को हटा देते हैं, और फिर NULL लौटाते हैं; अन्यथा, कोड जारी रहता है।

निष्कर्ष

इस ट्यूटोरियल में, हम रिकर्सन का उपयोग करके लंबाई