ধরুন আমাদের একটি বাইনারি ট্রি রুট আছে। একটি বাইনারি ট্রির জিগজ্যাগ পাথ নিচেরভাবে ডিফাইন করা হয় −
বাইনারি ট্রি-এ যেকোনো নোড এবং একটি ডিরেকশন (ডান বা বাম) বেছে নিন।
যতক্ষণ না ট্রিতে मूভ করা সম্ভব নয়, দ্বিতীয় ও তৃতীয় ধাপ রিপিট করুন।
এখানে জিগজ্যাগ দৈর্ঘ্য = ভিজিট করা নোডের সংখ্যা - ১। (একক নোডের দৈর্ঘ্য ০)। সেই ট্রিতে থাকা সবচেয়ে লম্বা জিগজ্যাগ পাথ বের করতে হবে। উদাহরণস্বরূপ, ট্রি নিচের মতো হলে −
আউটপুট হবে ৩, কারণ (Right, Left, Right)।
সমাধানের ধাপগুলো:
dfs() মেথড ডিফাইন করুন, যা root এবং leftB নেবে
যদি root null হয়, তবে -1 রিটার্ন করুন
যদি root ট্রিতে একক নোড হয়, তবে 0 রিটার্ন করুন
leftV := dfs(root-এর লেফট, true) এবং rightV := dfs(root-এর রাইট, false)
ret := max(ret, 1 + max(leftV, rightV))
যদি leftB true হয়, তবে 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; } }; 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
