C++ में बाइनरी ट्री में अधिकतम लगातार बढ़ती पथ लंबाई

मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें सबसे लंबे पथ की लंबाई की गणना करनी है जिसमें बढ़ते क्रम में लगातार मूल्यों के साथ नोड्स होते हैं। प्रत्येक नोड को लंबाई 1 के पथ के रूप में माना जाएगा।

तो, अगर इनपुट पसंद है

तो आउटपुट 3 होगा क्योंकि (11, 12, 13) अधिकतम क्रमागत पथ है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

एक फ़ंक्शन को हल करें परिभाषित करें (), यह रूट लेगा, prev_data, prev_length,
यदि जड़ शून्य नहीं है, तो −
- वापसी पिछला_लंबाई
cur_data :=जड़ का मान
यदि cur_data prev_data + 1 के समान है, तो −
- अधिकतम हल करें (रूट के बाएं, cur_data, prev_length+1) और हल करें (रूट का दायां, cur_data, prev_length+1)
newPathLen :=अधिकतम हल (रूट के बाएं, cur_data, 1) और हल (रूट का दायां, cur_data, 1)
अधिकतम prev_length और newPathLen लौटाएं
मुख्य विधि से निम्न कार्य करें -
यदि रूट NULL के समान है, तो −
- वापसी 0
रिटर्न सॉल्व (रूट, वैल ऑफ रूट-1, 0)

उदाहरण (C++)

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;
class TreeNode {
   public:
      int val;
      TreeNode *left, *right;
      TreeNode(int data) {
         val = data;
         left = NULL;
         right = NULL;
      }
};
int solve(TreeNode *root, int prev_data, int prev_length){
   if (!root)
      return prev_length;
   int cur_data = root->val;
   if (cur_data == prev_data+1){
      return max(solve(root->left, cur_data, prev_length+1), solve(root->right, cur_data, prev_length+1));
   }
   int newPathLen = max(solve(root->left, cur_data, 1), solve(root->right, cur_data, 1));
   return max(prev_length, newPathLen);
}
int maxLen(TreeNode *root){
   if (root == NULL)
      return 0;
   return solve(root, root->val-1, 0);
}
int main(){
   TreeNode *root = new TreeNode(10);
   root->left = new TreeNode(11);
   root->right = new TreeNode(9);
   root->left->left = new TreeNode(13);
   root->left->right = new TreeNode(12);
   root->right->left = new TreeNode(13);
   root->right->right = new TreeNode(8);
   cout << maxLen(root);
   return 0;
}

इनपुट

TreeNode *root = new TreeNode(10);
root->left = new TreeNode(11);
root->right = new TreeNode(9);
root->left->left = new TreeNode(13);
root->left->right = new TreeNode(12);
root->right->left = new TreeNode(13);
root->right->right = new TreeNode(8);