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

Cho gốc của một cây nhị phân với N nút, mỗi nút có node.val đồng xu, tổng cộng N đồng xu. Một phép di chuyển: chọn hai nút liền kề và chuyển một đồng xu từ nút này sang nút kia (có thể từ cha sang con hoặc ngược lại). Tìm số phép di chuyển tối thiểu để mỗi nút có đúng một đồng xu.

Ví dụ cây: gốc 0, con trái 3, con phải 0. Kết quả là 3. Từ con trái chuyển 2 đồng xu lên gốc (2 phép), sau đó từ gốc chuyển 1 đồng xu sang con phải (1 phép). Tổng 3 phép.

Giải thuật

• Định nghĩa hàm đệ quy solve(node):
  • Nếu node == null trả về 0.
  • l := solve(node->left), r := solve(node->right).
  • ans := |l| + |r|.
  • Trả về l + r + node->val - 1.
• Trong hàm chính: ans := 0, gọi solve(root), trả về ans.

Ví dụ mã C++

#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:
    int ans = 0;
    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;
    }
};

Đầu vào

[0,3,0]

Đầu ra

3