Phân phối xu trong cây nhị phân trong C ++

Giả sử chúng ta có gốc của cây nhị phân với N nút, ở đây mỗi nút trong cây có số lượng node.val là số đồng xu và có tổng số là N đồng. Trong một lần di chuyển, chúng ta có thể chọn hai nút liền kề và chỉ di chuyển một đồng tiền từ nút này sang nút khác. (Di chuyển có thể từ nút cha sang nút con hoặc từ nút con sang nút cha.). Chúng tôi phải tìm số lần di chuyển cần thiết để làm cho mỗi nút có đúng một đồng xu.

Vì vậy, nếu cây như -

Khi đó kết quả sẽ là 3. Từ con bên trái, gửi 2 đồng xu vào gốc (mỗi đồng xu một nước đi, nên tổng cộng 2 nước đi), sau đó chuyển một đồng từ gốc sang con phải, như vậy tổng cộng có 3 nước đi.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một phương thức đệ quy có tên là giải quyết (), phương thức này sẽ lấy một nút có tên là gốc
nếu gốc là null, thì trả về 0
l:=giải quyết (bên trái của thư mục gốc)
r:=giải quyết (bên phải của thư mục gốc)
ans:=| l | + | r |
trả về l + r + giá trị của gốc - 1
trong phần chính, đặt ans:=0, gọi giải quyết (root), sau đó trả về ans

Ví dụ

#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));
}

Đầu vào

[0,3,0]

Phân phối xu trong cây nhị phân trong C ++

Ví dụ

Đầu vào

Đầu ra