C++ में बाइनरी ट्री में सबसे लंबा जिगजैग पथ

मान लीजिए हमारे पास एक बाइनरी ट्री रूट है, बाइनरी ट्री के लिए एक जिगजैग पथ इस प्रकार परिभाषित है:

बाइनरी ट्री में किसी भी नोड और एक डायरेक्शन (या तो राइट या लेफ्ट) को चुनें।
अगर वर्तमान डायरेक्शन राइट है तो करंट नोड के राइट चाइल्ड की ओर बढ़ें अन्यथा लेफ्ट चाइल्ड की ओर बढ़ें।
फिर डायरेक्शन को राइट से लेफ्ट या वाइस वर्सा में बदलें।
दूसरे और तीसरे स्टेप्स को तब तक दोहराएं जब तक हम ट्री में मूव नहीं कर सकते।

यहां जिगजैग लंबाई को विजिटेड नोड्स की संख्या - 1 के रूप में परिभाषित किया गया है। (एक सिंगल नोड की लंबाई 0 होती है)। हमें उस ट्री में निहित सबसे लंबे जिगजैग पथ को ढूंढना है। उदाहरण के लिए, अगर ट्री है:

आउटपुट 3 होगा, जैसे (राइट, लेफ्ट, राइट)

इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:

dfs() नाम का एक मेथड डिफाइन करें, जो root और leftB लेगा
अगर रूट नल है, तो -1 लौटाएं
अगर रूट ट्री में केवल एक नोड है, तो 0 लौटाएं
leftV := dfs(root का लेफ्ट, true) और rightV := dfs(root का राइट, false)
ret := ret और (1 + leftV और rightV का मैक्स) का मैक्स
अगर leftB 0 नहीं है, तो 1 + rightV लौटाएं, अन्यथा 1 + leftV लौटाएं
मेन मेथड से, ret := 0 सेट करें
dfs(root, true) कॉल करें और dfs(root, false) कॉल करें
ret लौटाएं

उदाहरण (C++)

बेहतर समझ के लिए निम्न इम्प्लीमेंटेशन देखें:

#include <bits/stdc++.h>
using namespace std;

class TreeNode{
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data){
        val = data;
        left = right = NULL;
    }
};

void insert(TreeNode **root, int val){
    queue<TreeNode*> q;
    q.push(*root);
    while(q.size()){
        TreeNode *temp = q.front();
        q.pop();
        if(!temp->left){
            if(val != NULL)
                temp->left = new TreeNode(val);
            else
                temp->left = new TreeNode(0);
            return;
        } else {
            q.push(temp->left);
        }
        if(!temp->right){
            if(val != NULL)
                temp->right = new TreeNode(val);
            else
                temp->right = new TreeNode(0);
            return;
        } else {
            q.push(temp->right);
        }
    }
}

TreeNode *make_tree(vector<int> v){
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i<v.size(); i++){
        insert(&root, v[i]);
    }
    return root;
}

class Solution {
public:
    int ret;
    int dfs(TreeNode* root, bool leftB){
        if(!root) return -1;
        if(!root->left && !root->right) return 0;
        int leftV = dfs(root->left, true);
        int rightV = dfs(root->right, false);
        ret = max(ret, 1 + max(leftV, rightV));
        if(leftB) return 1 + rightV;
        return 1 + leftV;
    }
    int longestZigZag(TreeNode* root) {
        ret = 0;
        dfs(root, true);
        dfs(root, false);
        return ret;
    }
};

int main(){
    vector<int> v = {1,NULL,1,1,1,NULL,NULL,1,1,NULL,1,NULL,NULL,NULL,1,NULL,1};
    TreeNode *root = make_tree(v);
    Solution ob;
    cout << (ob.longestZigZag(root));
}

इनपुट

[1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]