Equal Tree Partition – ตรวจสอบการแบ่งต้นไม้ครึ่งๆ ใน C++

ปัญหา: Equal Tree Partition

กำหนด Binary Tree ตรวจสอบว่าสามารถ ตัดขอบ 1 ขอบ เพื่อแบ่งเป็น 2 ต้นไม้ที่ ผลรวมค่าโหนดเท่ากัน ได้หรือไม่

ตัวอย่าง

      5
     / \
    10  10
       /  \
      2    3

ตัดขอบระหว่าง 5 (ราก) กับ 10 (ขวา) → ซ้าย: 5+10=15, ขวา: 10+2+3=15 → true

แนวทางแก้ปัญหา: Post-order DFS + Subtree Sums

ข้อสังเกต

• ผลรวมทั้งหมด = total
• ตัดขอบใดขอบหนึ่ง → ได้ subtree sum = x, อีกฝั่ง = total - x
• ต้องการ x == total - x → 2x == total → x == total/2
• คำนวณ subtree sum ทุกโหนด → ตรวจสอบว่ามีโหนดไหน (ยกเว้นราก) ที่ sum = total/2

ขั้นตอน

1. DFS post-order คำนวณ subtree sum ทุกโหนด
2. เก็บ sum ทุกโหนดใน vector/stack
3. total = sum ของราก
4. ถ้า total เป็นเลขคี่ → false
5. ตรวจสอบว่ามี subtree sum (ยกเว้นราก) = total/2 หรือไม่

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
    vector<int> sums;

    int dfs(TreeNode* node) {
        if (!node) return 0;
        int leftSum = dfs(node->left);
        int rightSum = dfs(node->right);
        int curr = node->val + leftSum + rightSum;
        sums.push_back(curr);
        return curr;
    }

public:
    bool checkEqualTree(TreeNode* root) {
        sums.clear();
        int total = dfs(root);
        if (total % 2 != 0) return false;

        int target = total / 2;
        // sums.back() = total (root), skip it
        for (int i = 0; i < (int)sums.size() - 1; i++) {
            if (sums[i] == target) return true;
        }
        return false;
    }
};

int main() {
    Solution ob;
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(10);
    root->right = new TreeNode(10);
    root->right->left = new TreeNode(2);
    root->right->right = new TreeNode(3);
    cout << (ob.checkEqualTree(root) ? "true" : "false"); // true
    return 0;
}

ความซับซ้อน

• เวลา: O(N) – DFS ครั้งเดียว
• พื้นที่: O(N) – recursion stack + sums vector

ข้อสังเกต

• LeetCode 663
• สำคัญ: ต้อง ข้ามราก เพราะตัดขอบรากไม่ได้ (รากไม่มี parent)
• ใช้ long long ป้องกัน overflow ถ้าค่าโหนดใหญ่
• Post-order DFS เหมาะที่สุด – คำนวณลูกก่อน แล้วค่อยรวม