C++의 이진 트리에서 코인 배포

<시간/>

N개의 노드가 있는 이진 트리의 루트가 있다고 가정합니다. 여기서 트리의 각 노드에는 node.val 수의 코인이 있고 총 N개의 코인이 있습니다. 한 번의 이동으로 두 개의 인접한 노드를 선택하고 한 노드에서 다른 노드로 하나의 코인만 이동할 수 있습니다. (이동은 상위 노드에서 하위 노드로 또는 하위 노드에서 상위 노드로 수행될 수 있습니다.) 모든 노드가 정확히 하나의 코인을 갖도록 하는 데 필요한 이동 횟수를 찾아야 합니다.

트리가 다음과 같다면 -

그러면 출력은 3이 됩니다. 왼쪽 자식에서 루트로 2개의 코인을 보내고(각 코인에 대해 한 번 이동하므로 총 2번 이동) 루트에서 오른쪽 자식으로 동전 하나를 이동하여 총 3번 이동합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

solve()라는 재귀 메서드를 하나 정의하면 root라는 노드가 필요합니다.
루트가 null이면 0을 반환합니다.
l :=해결(루트 왼쪽)
r :=해결(루트 오른쪽)
답변 :=|l| + |r|
l + r + 루트 값 반환 – 1
기본 섹션에서 as :=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]