सी ++ पथ लंबाई जिसमें अधिकतम संख्या में मोड़ हैं

एक समस्या को हल करने के लिए जिसमें हमें एक बाइनरी ट्री दिया जाता है। अब हमें उस पथ को खोजने की आवश्यकता है जिसमें अधिकतम संख्या में मोड़ हों। यानी, एक मोड़ तब माना जाता है जब पथ की दिशा बाएं से दाएं या इसके विपरीत बदलती है, उदाहरण के लिए

इनपुट -

आउटपुट -

अब इस दृष्टिकोण में, हम पेड़ से गुजरेंगे और पिछले आंदोलनों का ट्रैक रखेंगे। यदि दिशा बदल जाती है, तो हम बस अपने मोड़ों की संख्या को अपडेट करते हैं, और फिर हम अधिकतम पाते हैं।

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

इस दृष्टिकोण में, हम सभी रास्तों से गुजरेंगे, और हम अपने उत्तर को अपडेट करने के लिए अधिकतम संख्या में मोड़ पाते हैं।

उदाहरण

#include <bits/stdc++.h>
using namespace std;
struct Node { // structure of our node
    int key;
    struct Node* left;
    struct Node* right;
};
struct Node* newNode(int key){ // initializing our node
    struct Node* node = new Node();
    node->left = NULL;
    node->right = NULL;
    node->key = key;
    return node;
}
void maximumBends(struct Node* node,char direction, int bends,
                    int* maxBends, int soFar,int* len){
    if (node == NULL) // if null is reached
       return;
    if (node->left == NULL && node->right == NULL) { // if we reach the leaf node then
                                                   //we check if we have to update our answer or not
        if (bends > *maxBends) {
            *maxBends = bends;
            *len = soFar;
        }
    }
    else {
        if (direction == 'l') { // current direction is left
            maximumBends(node->left, direction,bends, maxBends,soFar + 1, len);
            maximumBends(node->right, 'r',bends + 1, maxBends,soFar + 1, len); // if we change direction so bend also increases
        }
        else {
            maximumBends(node->right, direction,bends, maxBends,soFar + 1, len);
            maximumBends(node->left, 'l',bends + 1, maxBends,soFar + 1, len); // same as when direction was left
        }
    }
}
int main(){
    struct Node* root = newNode(10);
    root->left = newNode(8);
    root->right = newNode(2);
    root->left->left = newNode(3);
    root->left->right = newNode(5);
    root->right->left = newNode(2);
    root->right->left->right = newNode(1);
    root->right->left->right->left = newNode(9);
    int len = 0, bends = 0, maxBends = -1;
    if(!root) // if tree is empty
       cout << "0\n";
    else{
        if (root->left) // if left subtree exists
            maximumBends(root->left, 'l',bends, &maxBends, 1, &len);
        if (root->right) // if right subtree exists
            maximumBends(root->right, 'r', bends,&maxBends, 1, &len);
        cout << len << "\n";
    }
    return 0;
}

आउटपुट

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

उपरोक्त दृष्टिकोण में, हम बस सभी पथों को पार कर रहे हैं और अब तक पाए गए मोड़ को गिनते हैं जब हम पथ के अंत तक पहुंचते हैं। कंडीशन सही है, इसलिए हम अपने अधिकतम मोड़ और पथ की लंबाई को इस नई लंबाई तक अपडेट करते हैं, और इस तरह हमारा प्रोग्राम आगे बढ़ता है।

निष्कर्ष

इस ट्यूटोरियल में, हम अधिकतम संख्या में मोड़ वाले पथ की लंबाई को खोजने के लिए एक समस्या का समाधान करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और संपूर्ण दृष्टिकोण (Normal) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम उसी प्रोग्राम को अन्य भाषाओं जैसे सी, जावा, पायथन और अन्य भाषाओं में लिख सकते हैं। हमें उम्मीद है कि आपको यह ट्यूटोरियल मददगार लगा होगा।