C++ में समान वृक्ष विभाजन

मान लीजिए कि हमारे पास n नोड्स के साथ एक बाइनरी ट्री है, तो हमारा काम यह जांचना है कि क्या ट्री को दो पेड़ों में विभाजित करना संभव है, जिनका मूल पेड़ के ठीक एक किनारे को हटाने के बाद बराबर योग है।

तो, अगर इनपुट पसंद है

तब आउटपुट सही होगा।

• इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक स्टैक सेंट परिभाषित करें

• एक फ़ंक्शन हल करें () को परिभाषित करें, यह नोड लेगा,

• यदि नोड शून्य है, तो -

  • वापसी 0

• लेफ्टसम:=हल करें (नोड के बाएं)

• राइटसम:=हल करें (नोड के दाएं)

• curr :=वैल + लेफ्टसम + राइटसम ऑफ नोड

• सेंट में करंट डालें

• वापसी वक्र

• मुख्य विधि से निम्न कार्य करें -

• हल (रूट)

• TotalSum :=सेंट का शीर्ष तत्व

• सेंट से तत्व हटाएं

• जबकि (सेंट खाली नहीं है), करें -

  • x:=सेंट का शीर्ष तत्व

  • सेंट से तत्व हटाएं

  • 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