C++での等しいツリーパーティション

n個のノードを持つ二分木があるとすると、元のツリーの1つのエッジを削除した後、値の合計が等しい2つのツリーにツリーを分割できるかどうかを確認するタスクがあります。

したがって、入力が次のような場合

そうすれば、出力は真になります。

• これを解決するには、次の手順に従います-

• 1つのスタックstを定義する

• 関数solve（）を定義します。これはノードを取ります

• ノードがnullの場合、-

  • 0を返す

• leftSum：=solve（ノードの左側）

• rightSum：=solve（ノードの権利）

• curr：=val + leftSum+rightSumのノード

• stにcurrを挿入します

• リターンカー

• メインの方法から、次のようにします-

• 解決（ルート）

• totalSum：=stの最上位要素

• stから要素を削除

• （stが空ではない）間、-

  • x：=stの最上位要素

  • stから要素を削除

  • y：=totalSum-x <​​/ P>

  • 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