मान लीजिए कि हमारे पास एक बाइनरी ट्री रूट है, एक बाइनरी ट्री के लिए एक ज़िगज़ैग पथ को निम्नानुसार परिभाषित किया गया है -
-
बाइनरी ट्री और दिशा में कोई भी नोड चुनें (दाएं या बाएं)।
-
यदि वर्तमान दिशा सही है तो वर्तमान नोड के दाहिने बच्चे की ओर बढ़ो अन्यथा बाएं बच्चे की ओर बढ़ो।
-
फिर दिशा को दाएं से बाएं या इसके विपरीत दिशा बदलें।
-
दूसरे और तीसरे चरण को तब तक दोहराएं जब तक कि हम पेड़ में नहीं जा सकते।
यहाँ ज़िगज़ैग लंबाई को विज़िट किए गए नोड्स की संख्या के रूप में परिभाषित किया गया है - 1. (एक एकल नोड की लंबाई 0 है)। हमें उस पेड़ में निहित सबसे लंबा ज़िगज़ैग पथ खोजना होगा। तो उदाहरण के लिए, यदि पेड़ की तरह है -
आउटपुट 3 होगा, जैसे (दाएं, बाएं, दाएं)
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
डीएफएस () नामक एक विधि को परिभाषित करें, यह रूट और लेफ्ट ले जाएगाबी
-
यदि रूट शून्य है, तो -1
. लौटाएं -
यदि पेड़ में जड़ केवल एक नोड है, तो 0
-
बायां वी:=डीएफएस (रूट के बाएं, सत्य) और दाएं वी:=डीएफएस (रूट का दायां, झूठा)
-
ret :=अधिकतम रिट और (1 + अधिकतम बाएँV और दाएँV)
-
अगर बायां बी 0 नहीं है, तो 1 + दायां वी लौटाएं, अन्यथा 1 + बाएं वी वापस करें
-
मुख्य विधि से, रिट सेट करें:=0
-
कॉल dfs(root, true) और कॉल dfs(root, false)
-
वापसी रिट
उदाहरण (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;
}
};
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]
आउटपुट
3