ধরুন আমাদের এন নোড সহ একটি বাইনারি ট্রি আছে, আমাদের কাজ হল মূল গাছের ঠিক একটি প্রান্ত মুছে ফেলার পরে ট্রিটিকে দুটি ট্রিতে ভাগ করা সম্ভব কিনা তা পরীক্ষা করা।
সুতরাং, যদি ইনপুট মত হয়
তাহলে আউটপুট সত্য হবে।
-
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি স্ট্যাক স্ট্যাক সংজ্ঞায়িত করুন
-
একটি ফাংশন সংজ্ঞায়িত করুন সমাধান(), এটি নোড নেবে,
-
যদি নোড নাল হয়, তাহলে −
-
রিটার্ন 0
-
-
leftSum :=সমাধান (নোডের বামে)
-
rightSum :=সমাধান (নোডের ডানদিকে)
-
curr :=val + leftSum + rightSum of node
-
st
এ curr ঢোকান -
রিটার্ন curr
-
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
-
সমাধান(রুট)
-
totalSum :=st এর শীর্ষ উপাদান
-
st
থেকে উপাদান মুছুন -
যখন (st খালি নয়), −
করুন-
x :=st
এর শীর্ষ উপাদান -
st
থেকে উপাদান মুছুন -
y :=মোট যোগফল - x
-
যদি x y এর সমান হয়, তাহলে −
-
প্রত্যাবর্তন সত্য
-
-
-
ফেরত মিথ্যা
উদাহরণ
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#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:
stack <int> st;
int solve(TreeNode* node){
if (!node)
return 0;
int leftSum = solve(node->left);
int rightSum = solve(node->right);
int curr = node->val + leftSum + rightSum;
st.push(curr);
return curr;
}
bool checkEqualTree(TreeNode* root) {
solve(root);
int totalSum = st.top();
st.pop();
while (!st.empty()) {
int x = st.top();
st.pop();
int y = totalSum - x;
if (x == y)
return true;
}
return false;
}
};
main(){
Solution ob;
TreeNode *root = new TreeNode(5);
root->left = new TreeNode(10);
root->right = new TreeNode(10);
root->right->left = new TreeNode(2);
root->right->right = new TreeNode(3);
cout<<(ob.checkEqualTree(root));
} ইনপুট
TreeNode *root = new TreeNode(5); root->left = new TreeNode(10); root->right = new TreeNode(10); root->right->left = new TreeNode(2); root->right->right = new TreeNode(3);
আউটপুট
1
