C++ এ বাইনারি ট্রিতে সর্বাধিক মূল্যের শিকড় গণনা করা হচ্ছে

ধরুন আমাদের একটি বাইনারি গাছের মূল আছে; আমাদের নোডের সংখ্যা গণনা করতে হবে যেখানে এর মান তার সমস্ত বংশধরের মানের থেকে বেশি বা সমান।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে 4টি নোড ছাড়া 3টি, এটি মানদণ্ড পূরণ করে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি ফাংশন সংজ্ঞায়িত করুন dfs(), এটি নোড নেবে,
যদি নোড নাল না হয়, তাহলে −
- ফেরত 0
l :=dfs (নোডের বামে)
r :=dfs (নোডের ডানদিকে)
যদি নোডের ভ্যাল>=l এবং r এর সর্বোচ্চ হয়, তাহলে −
- (রেট 1 দ্বারা বৃদ্ধি করুন)
x :=নোড, l এবং r
এর সর্বোচ্চ ভ্যাল
রিটার্ন x
প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন,
ret :=0
dfs(root)
রিটার্ন রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class TreeNode {
   public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data) {
      val = data;
      left = NULL;
      right = NULL;
   }
};
class Solution {
   public:
   int ret;
   int dfs(TreeNode* node){
      if(!node)
         return 0;
      int l = dfs(node->left);
      int r = dfs(node->right);
      if(node->val >= max(l, r)) {
         ret++;
      }
      int x = max({node->val, l, r});
      return x;
   }
   int solve(TreeNode* root) {
      ret = 0;
      dfs(root);
      return ret;
   }
};
main(){
   Solution ob;
   TreeNode *root = new TreeNode(7);
   root->left = new TreeNode(4);
   root->right = new TreeNode(3);
   root->right->left = new TreeNode(7);
   root->right->right = new TreeNode(5);
   cout << (ob.solve(root));
}

ইনপুট

TreeNode *root = new TreeNode(7);
root->left = new TreeNode(4);
root->right = new TreeNode(3);
root->right->left = new TreeNode(7);
root->right->right = new TreeNode(5);