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

समस्या विवरण

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

उदाहरण

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

एल्गोरिदम चरण

फ़ंक्शन solve(root, prev_data, prev_length) परिभाषित करें:
- यदि root शून्य है, तो prev_length वापस करें
- cur_data := root का मान
- यदि cur_data == prev_data + 1:
  - solve(left, cur_data, prev_length+1) और solve(right, cur_data, prev_length+1) का अधिकतम वापस करें
- newPathLen := solve(left, cur_data, 1) और solve(right, cur_data, 1) का अधिकतम
- prev_length और newPathLen का अधिकतम वापस करें
मुख्य विधि से:
- यदि root NULL है, तो 0 वापस करें
- solve(root, root->val - 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);