C++-এ Maximum Difference Between Node and Ancestor

ধরি আমাদের একটি বাইনারি ট্রির রুট আছে, আমাদের ম্যাক্সিমাম ভ্যালু V বের করতে হবে যাতে ভিন্ন নোড A এবং B وجود করে যেখানে V = |value of A – value of B| এবং A হল B-এর আনসিস্টর। ট্রি যদি নিচের মত হয়:

তবে আউটপুট হবে ৭। আনসিস্টর নোড ডিফারেন্সগুলো হল [(8 - 3), (7 - 3), (8 - 1), (10-13)], 그중 থেকে (8 - 1) = 7 ম্যাক্সিমাম।

এটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:

• শুরুতে ans 0 ডিফাইন করুন

• একটি solve() মেথড ডিফাইন করুন, এটি ট্রি নোড, currMin এবং currMax নিবে। এটি নিচের মত কাজ করবে:

• যদি নোড null হয়, তবে রিটার্ন করুন

• ans := max(ans, |value of node - currMin|, |value of node - currMax|)

• solve(left of node, min(node value, currMin), max(node value, currMax))

• solve(right of node, min(node value, currMin), max(node value, currMax))

• মেইন সেকশনে, solve(root, value of root, value of 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;
    }
};

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 ans;
    void solve(TreeNode* node, int currMin, int currMax) {
        if (!node || node->val == 0) return;
        ans = max({ans, abs(node->val - currMin), abs(node->val - currMax)});
        solve(node->left, min(node->val, currMin), max(node->val, currMax));
        solve(node->right, min(node->val, currMin), max(node->val, currMax));
    }
    int maxAncestorDiff(TreeNode* root) {
        ans = 0;
        solve(root, root->val, root->val);
        return ans;
    }
};

int main() {
    vector<int> v = {8,3,10,1,6,NULL,14,NULL,NULL,4,7,13};
    TreeNode *root = make_tree(v);
    Solution ob;
    cout << (ob.maxAncestorDiff(root));
}

ইনপুট

[8,3,10,1,6,null,14,null,null,4,7,13]

আউটপুট

7