मान लीजिए हमारे पास n नोड्स वाला एक बाइनरी ट्री है, हमारा कार्य यह जांचना है कि क्या मूल ट्री पर ठीक एक किनारा हटाकर ट्री को दो ट्री में विभाजित करना संभव है जिनके मानों का योग समान हो।
उदाहरण के लिए, यदि इनपुट दिए गए चित्र के अनुसार है, तो आउटपुट true होगा।
हल करने की विधि
हम पोस्ट-ऑर्डर ट्रैवर्सल का उपयोग करके प्रत्येक उपट्री का योग गणना करेंगे:
- एक स्टैक st परिभाषित करें।
solve()फ़ंक्शन नोड लेता है, उसके बाएं और दाएं उपट्री के योग की गणना करता है, वर्तमान योग = मान + बायां योग + दायां योग, स्टैक में डालता है, और वर्तमान योग लौटाता है।- मुख्य विधि में:
- solve(root) कॉल करें।
- कुल योग = स्टैक का शीर्ष तत्व, पॉप करें।
- जब तक स्टैक खाली न हो: शीर्ष तत्व x निकालें, y = कुल योग - x। यदि x == y, तो true लौटाएं।
- false लौटाएं।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#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
