একটি গাছ উচ্চতা ভারসাম্যপূর্ণ কিনা তা পরীক্ষা করার জন্য প্রোগ্রাম C++ এ

ধরুন আমাদের একটি বাইনারি গাছ আছে; আমাদের পরীক্ষা করতে হবে এর উচ্চতা ভারসাম্যপূর্ণ কি না। আমরা জানি যে একটি উচ্চতা ভারসাম্যপূর্ণ গাছের জন্য, গাছের প্রতিটি নোডের জন্য, এর বাম উপবৃক্ষের উচ্চতা এবং ডান উপবৃক্ষের উচ্চতার পরম পার্থক্য হল 0 বা 1৷

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

তাহলে আউটপুট হবে True

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

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

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

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class TreeNode {
   public:
   int val;
   TreeNode *left;
   TreeNode *right;
   TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
   public:
   bool ret;
   int dfs(TreeNode* node){
      if(!node)
         return 0;
      int l = 1 + dfs(node->left);
      int r = 1 + dfs(node->right);
      if(abs(l - r) > 1)
         ret = false;
      return max(l, r);
   }
   bool isBalanced(TreeNode* root) {
      ret = true;
      dfs(root);
      return ret;
   }
};
main(){
   Solution ob;
   TreeNode *root = new TreeNode(25);
   root->left = new TreeNode(19);
   root->right = new TreeNode(4);
   root->left->left = new TreeNode(9);
   root->left->right = new TreeNode(7);
   cout << (ob.isBalanced(root));
}

ইনপুট

TreeNode *root = new TreeNode(25);
root->left = new TreeNode(19);
root->right = new TreeNode(4);
root->left->left = new TreeNode(9);
root->left->right = new TreeNode(7);