C++のバイナリツリーでコインを配布する

N個のノードを持つ二分木のルートがあるとします。ここでは、ツリー内の各ノードにnode.val個のコインがあり、合計でN個のコインがあります。 1回の移動で、隣接する2つのノードを選択し、1つのノードから別のノードに1つのコインのみを移動できます。 （移動は、親から子ノードへ、または子から親ノードへの移動である可能性があります。）すべてのノードが正確に1枚のコインを持つようにするために必要な移動数を見つける必要があります。

したがって、ツリーが次のような場合-

次に、出力は3になります。左の子から2枚のコインをルートに送信し（コインごとに1枚の移動、つまり合計2枚の移動）、次に1枚のコインをルートから右の子に移動します。合計で3回の移動があります。

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

• solve（）と呼ばれる1つの再帰メソッドを定義します。これはrootと呼ばれるノードを取ります

• ルートがnullの場合、0を返します

• l：=solve（ルートの左側）

• r：=solve（ルートの右側）

• ans：=| l | + | r |

• l + r +ルートの値を返す– 1

• メインセクションで、ans：=0を設定し、solve（root）を呼び出してから、ansを返します

例

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = NULL;
      right = NULL;
   }
};
void insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
      }else{
         q.push(temp->left);
      }
      if(!temp->right){
         if(val != NULL)
            temp->right = new TreeNode(val);
         else
            temp->right = new TreeNode(0);
         return;
      }else{
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int> v){
   TreeNode *root = new TreeNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
class Solution {
   public:
   int ans;
   int solve(TreeNode* root){
      if(!root)return 0;
      int l = solve(root->left);
      int r = solve(root->right);
      ans += abs(l) + abs(r);
      return l + r + root->val - 1;
   }
   int distributeCoins(TreeNode* root) {
      ans = 0;
      solve(root);
      return ans;
   }
};
main(){
   vector<int> v = {0,3,0};
   TreeNode *root = make_tree(v);
   Solution ob;
   cout << (ob.distributeCoins(root));
}   

入力

[0,3,0]

出力

3