การกระจายเหรียญในต้นไม้แบนารีใน C++

ปัญหาการกระจายเหรียญในต้นไม้แบนารี (Distribute Coins in Binary Tree)

ให้รากของต้นไม้แบนารีที่มี N โหนด แต่ละโหนดมีค่า node.val แทนจำนวนเหรียญ รวมเหรียญทั้งหมด N เหรียญ ในหนึ่งการเคลื่อนย้าย สามารถเลือกโหนดที่อยู่ติดกันสองโหนด และย้ายเหรียญหนึ่งเหรียญจากโหนดหนึ่งไปอีกโหนด (อาจเป็นจากพ่อไปลูก หรือลูกไปพ่อ) ต้องการหาจำนวนการเคลื่อนย้ายขั้นต่ำเพื่อให้ทุกโหนดมีเหรียญพอดี 1 เหรียญ

ตัวอย่าง: ต้นไม้ [0,3,0] ผลลัพธ์คือ 3 จากโหนดลูกซ้ายส่ง 2 เหรียญไปราก (2 ครั้ง) แล้วรากส่ง 1 เหรียญไปลูกขวา (1 ครั้ง) รวม 3 ครั้ง

ขั้นตอนการแก้ปัญหา (DFS แบบ Post-order)

1. กำหนดฟังก์ชันเวียนเกิด solve(root):
2. ถ้า root == null คืนค่า 0
3. l := solve(root.left), r := solve(root.right)
4. ans := |l| + |r| (สะสมจำนวนการเคลื่อนย้าย)
5. คืนค่า l + r + root.val - 1 (เหรียญส่วนเกิน/ขาดที่ต้องส่งต่อให้พ่อ)
6. ในฟังก์ชันหลัก: ans := 0, เรียก solve(root), คืนค่า ans

ตัวอย่างโค้ด 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;
    }
};

อินพุทและเอาต์พุทตัวอย่าง

Input: [0,3,0]

Output: 3