C++-এ জোড় মানযুক্ত দাদানODE-এর সatgesের যোগফল

মনে করুন একটি বাইনারি ট্রি আছে, আমাদের জোড় মানযুক্ত দাদা-নোড (grandparent) থাকা নোডগুলির মানগুলোর যোগফল বের করতে হবে। (একটি নোডের দাদা হলো তার পেরেন্টের পেরেন্ট, যদি বিদ্যমান থাকে।) যদি এমন কোনো নোড না থাকে যার দাদার মান জোড়, তবে ০ রিটার্ন করুন। যদি ট্রি নিচের মোতাবিক হয় -

আউটপুট হবে ১৮। লাল নোডগুলো হলো জোড় মানযুক্ত দাদা-নোড रखা নোডগুলো, নীল নোডগুলো হলো জোড় মানযুক্ত দাদা-নোডগুলো।

এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব -

একটি `parent` নামক ম্যাপ সংজ্ঞায়িত করুন
`solve()` নামক একটি মেথড সংজ্ঞায়িত করুন, যা `node` এবং `par` প্যারামিটার নেবে
যদি `node` null হয়, তবে রিটার্ন করুন
যদি `par` null না হয় এবং `par` `parent` ম্যাপে বিদ্যমান থাকে এবং `parent[par]` ০ না হয় এবং `parent[par]`-এর মান জোড় হয়, তবে
- `res := res + node`-এর মান
`parent[node] := par`
`solve(node`-এর বাম, `node`)
`solve(node`-এর ডান, `node`)
মেইন মেথড থেকে `res := 0` সেট করুন, `solve(root, Null)` কল করুন, তারপর `res` রিটার্ন করুন

উদাহরণ (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;       } }; 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 res;    map <TreeNode*, TreeNode*> parent;    void solve(TreeNode* node, TreeNode* par = NULL){       if(!node)return;       if(par && parent.count(par) && parent[par] && parent[par]->val % 2 == 0){          res += node->val;       }       parent[node] = par;       solve(node->left, node);       solve(node->right, node);    }    int sumEvenGrandparent(TreeNode* root) {       res = 0;       parent.clear();       solve(root);       return res;    } }; main(){    vector<int> v = {6,7,8,2,7,1,3,9,NULL,1,4,NULL,NULL,NULL,5};    TreeNode *root = make_tree(v);    Solution ob;    cout << (ob.sumEvenGrandparent(root)); }

ইনপুট

[6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]