मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें उस बाइनरी ट्री में सबसे लंबे लगातार पथ की लंबाई का पता लगाना है। यहां रास्ता या तो बढ़ सकता है या घट सकता है। तो एक उदाहरण के रूप में [1,2,3,4] और [4,3,2,1] दोनों को एक वैध पथ माना जाता है, लेकिन पथ [1,2,4,3] मान्य नहीं है।
अन्यथा, पथ बाल-माता-पिता-बाल अनुक्रम में हो सकता है, जहां जरूरी नहीं कि माता-पिता-बाल क्रम हो।
तो, अगर इनपुट पसंद है
तो आउटपुट 3 होगा क्योंकि लगातार सबसे लंबा पथ [1, 2, 3] या [3, 2, 1] जैसा होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक फ़ंक्शन को परिभाषित करें सॉल्वयूटिल (), यह नोड लेगा,
-
यदि नोड शून्य है, तो -
-
वापसी { 0, 0 }
-
-
बायां =हल करें (नोड के बाएं)
-
बाएं =हल करें (नोड के दाएं)
-
एक जोड़ी अस्थायी परिभाषित करें:={1,1}
-
यदि नोड के बाईं ओर मौजूद है और नोड के बाईं ओर का मान नोड + 1 के मान के समान है, तो -
-
temp.first :=अधिकतम temp.first और 1 + left.first
-
उत्तर:=अधिकतम उत्तर और अस्थायी। पहले
-
-
यदि नोड का अधिकार मौजूद है और नोड के अधिकार का मान नोड + 1 के मान के समान है, तो -
-
temp.first :=अधिकतम temp.first और 1 + right.first
-
उत्तर:=अधिकतम उत्तर और अस्थायी। पहले
-
-
यदि नोड के बाईं ओर मौजूद है और नोड के बाईं ओर का मान नोड -1 के मान के समान है, तो -
-
temp.second :=अधिकतम temp.second और 1 + left.second
-
Ans :=अधिकतम ans और temp.second
-
-
यदि नोड का अधिकार मौजूद है और नोड के अधिकार का मान नोड -1 के मान के समान है, तो -
-
temp.second :=अधिकतम temp.second और 1 + right.second
-
Ans :=अधिकतम ans और temp.second
-
-
उत्तर:=अधिकतम { ans और temp.first + temp.second - 1 }
-
वापसी अस्थायी
-
मुख्य विधि से निम्न कार्य करें -
-
उत्तर :=0
-
हल करें (रूट)
-
वापसी उत्तर
उदाहरण
आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -
#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