在C ++中以二叉树分发硬币

假设我们有一棵具有N个节点的二叉树的根，这里树中的每个节点都有node.val个硬币，总共有N个硬币。一口气，我们可以选择两个相邻的节点，并且只能将一个硬币从一个节点移动到另一个节点。（此移动可能是从父节点到子节点，或从子节点到父节点。）。我们必须找到使每个节点恰好具有一个硬币所需的移动次数。

所以如果树像-

然后输出将为3。从左子节点向根发送2个硬币（每个硬币一动，所以总共2步），然后从根向右子节点移动一个硬币，因此总共有3步。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个称为的递归方法solve()，它将采用一个称为root的节点

• 如果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