मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें उस बाइनरी ट्री में सबसे लंबे लगातार पथ की लंबाई ढूंढनी है। यहां पथ या तो बढ़ता हुआ या घटता हुआ हो सकता है। इसलिए उदाहरण के लिए [1,2,3,4] और [4,3,2,1] दोनों को वैध पथ माना जाता है, लेकिन पथ [1,2,4,3] वैध नहीं है।
अन्यथा, पथ चाइल्ड-पैरेंट-चाइल्ड अनुक्रम में हो सकता है, जहां पैरेंट-चाइल्ड क्रम आवश्यक नहीं है।
उदाहरण के लिए, यदि इनपुट दिए गए चित्र के अनुसार है, तो आउटपुट 3 होगा क्योंकि सबसे लंबा लगातार पथ [1, 2, 3] या [3, 2, 1] जैसा होगा।
हल करने की विधि
हम रिकर्सिव दृष्टिकोण का उपयोग करेंगे:
solveUtil()फ़ंक्शन नोड लेता है और एक युग्म लौटाता है: (बढ़ता हुआ पथ लंबाई, घटता हुआ पथ लंबाई)।- यदि नोड null है, तो {0,0} लौटाएं।
- बाएं और दाएं के लिए रिकर्सिवली कॉल करें।
- temp = {1,1} प्रारंभ करें।
- यदि बायां बच्चा मौजूद है और उसका मान नोड के मान + 1 के बराबर है, तो temp.first अपडेट करें और ans अपडेट करें।
- यदि दायां बच्चा मौजूद है और उसका मान नोड के मान + 1 के बराबर है, तो temp.first अपडेट करें और ans अपडेट करें।
- यदि बायां बच्चा मौजूद है और उसका मान नोड के मान - 1 के बराबर है, तो temp.second अपडेट करें और ans अपडेट करें।
- यदि दायां बच्चा मौजूद है और उसका मान नोड के मान - 1 के बराबर है, तो temp.second अपडेट करें और ans अपडेट करें।
- ans = max(ans, temp.first + temp.second - 1)।
- temp लौटाएं।
- मुख्य विधि में: ans = 0, solveUtil(root) कॉल करें, ans लौटाएं।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; class TreeNode{ public: int val; TreeNode *left, *right; TreeNode(int data){ val = data; left = NULL; right = NULL; } }; class Solution { public: int ans = 0; pair<int, int> solveUtil(TreeNode* node){ if (!node) { return { 0, 0 }; } pair<int, int> left = solveUtil(node->left); pair<int, int> right = solveUtil(node->right); pair<int, int> temp = { 1, 1 }; if (node->left && node->left->val == node->val + 1) { temp.first = max(temp.first, 1 + left.first); ans = max(ans, temp.first); } if (node->right && node->right->val == node->val + 1) { temp.first = max(temp.first, 1 + right.first); ans = max(ans, temp.first); } if (node->left && node->left->val == node->val - 1) { temp.second = max(temp.second, 1 + left.second); ans = max(ans, temp.second); } if (node->right && node->right->val == node->val - 1) { temp.second = max(temp.second, 1 + right.second); ans = max(ans, temp.second); } ans = max({ ans, temp.first + temp.second - 1 }); return temp; } int longestConsecutive(TreeNode* root){ ans = 0; solveUtil(root); return ans; } }; main(){ Solution ob; TreeNode *root = new TreeNode(2); root->left = new TreeNode(1); root->right = new TreeNode(3); cout << (ob.longestConsecutive(root)); }
इनपुट
TreeNode *root = new TreeNode(2); root->left = new TreeNode(1); root->right = new TreeNode(3);
आउटपुट
3
