ধরুন আমাদের একটি বাইনারি ট্রি আছে, গাছের একটি নোড X-এর নাম দেওয়া হয়েছে ভাল যখন রুট থেকে X এর পথে এমন কোনও নোড নেই যার মান X-এর চেয়ে বেশি। এখানে আমাদের বাইনারি গাছে ভাল নোডের সংখ্যা খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুট মত হয়,
তাহলে আউটপুট হবে 4, রঙিন নোডগুলো ভালো নোড।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি ফাংশন dfs() সংজ্ঞায়িত করুন, এটি নোড, ভ্যাল,
নেবে -
যদি নোড নাল হয়, তাহলে −
-
ফেরত
-
-
ret :=ret + (1 যখন val <=নোডের val, অন্যথায় 0)
-
dfs(নোডের বাম, সর্বোচ্চ ভাল এবং নোডের ভাল)
-
dfs(নোডের ডান, সর্বোচ্চ ভ্যাল এবং নোডের ভাল)
-
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
-
ret :=0
-
dfs(root, -inf)
-
রিটার্ন রিটার্ন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#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 ret;
void dfs(TreeNode* node, int val){
if (!node)
return;
ret += val <= node->val;
dfs(node->left, max(val, node->val));
dfs(node->right, max(val, node->val));
}
int goodNodes(TreeNode* root){
ret = 0;
dfs(root, INT_MIN);
return ret;
}
};
main(){
Solution ob;
vector<int> v = {3,1,4,3,NULL,1,5};
TreeNode *root = make_tree(v);
cout << (ob.goodNodes(root));
} ইনপুট
{3,1,4,3,NULL,1,5} আউটপুট
4
