C++ এ বাইনারি গাছের ডান পাতার যোগফল খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি গাছ আছে আমাদের একটি প্রদত্ত বাইনারি গাছের সমস্ত সঠিক পাতার যোগফল খুঁজে বের করতে হবে৷

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

তাহলে আউটপুট হবে 17, কারণ বাইনারি গাছে দুটি ডান পাতা রয়েছে, যার মান যথাক্রমে 7 এবং 10।

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

একটি ফাংশন সংজ্ঞায়িত করুন dfs(), এটি নোড, যোগ,
নেবে
যদি নোড নাল হয়, তাহলে −
- ফেরত
যদি নোডের বাম অংশটি নাল হয় এবং নোডের ডানদিকে শূন্য হয় এবং যোগ অ-শূন্য হয়, তাহলে −
- ret :=ret + নোডের val
dfs(নোডের বাম, মিথ্যা)
dfs(নোডের ডান, সত্য)
প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
ret :=0
dfs(রুট, সত্য)
রিটার্ন রিটার্ন

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

উদাহরণ

#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 = 0;
   void dfs(TreeNode* node, bool add){
      if(!node)
      return ;
      if(!node−>left && !node->right && add){
         ret += node−>val;
      }
      dfs(node−>left, false);
      dfs(node−>right, true);
   }
   int solve(TreeNode* root) {
      ret = 0;
      dfs(root, true);
      return ret;
   }
};
main(){
   Solution ob;
   TreeNode *root = new TreeNode(3);
   root−>left = new TreeNode(9);
   root−>right = new TreeNode(10);
   root−>left−>left = new TreeNode(15);
   root−>left−>right = new TreeNode(7);
   cout << (ob.solve(root));
}

ইনপুট

TreeNode *root = new TreeNode(3);
root−>left = new TreeNode(9);
root−>right = new TreeNode(10);
root−>left−>left = new TreeNode(15);
root−>left−>right = new TreeNode(7);