Path Sum IV – ผลรวมเส้นทางในต้นไม้เข้ารหัส 3 หลัก C++

ปัญหา: Path Sum IV

ต้นไม้ความลึก < 5 เข้ารหัสเป็นรายการจำนวน 3 หลัก:
- หลักร้อย = ความลึก D (1-4)
- หลักสิบ = ตำแหน่ง P ในระดับ (1-8, เหมือน full binary tree)
- หลักหน่วย = ค่า V (0-9)

หา ผลรวมเส้นทางจากรากถึงใบทุกเส้นทาง

ตัวอย่าง

Input: [113, 215, 221]

Depth 1: 1 (pos 1, val 3)     → 113
Depth 2: 2 (pos 1, val 5)     → 215
       2 (pos 2, val 1)     → 221

Tree:
      3
     / \
    5   1

Paths: 3→5 = 8, 3→1 = 4 → Sum = 12

แนวทางแก้ปัญหา: Build Tree แล้ว DFS

การเข้ารหัสตำแหน่ง

ใน Full Binary Tree, โหนดที่ depth d, position p มี index (1-based) = 2^(d-1) + p - 1
ลูกซ้าย = index×2, ลูกขวา = index×2+1
→ ตรวจสอบ parent-child: child_index / 2 == parent_index

ขั้นตอน

1. Parse แต่ละจำนวน → (level, pos, val)
2. คำนวณ index = (1 << (level-1)) + pos - 1
3. จัดกลุ่มตาม level: graph[level].push_back({index, val})
4. DFS จาก root (level 1):
   • หาลูกใน level+1 ที่ child_index / 2 == parent_index
   • สะสม sum
   • ถ้าเป็นใบ (ไม่มีลูก) → บวก sum เข้าคำตอบ

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

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

class Solution {
    int ans = 0;
    unordered_map<int, vector<pair<int,int>>> levelNodes; // level -> [(index, val)]

    void dfs(int nodeVal, int level, int index, int sum) {
        sum += nodeVal;
        bool isLeaf = true;

        if (levelNodes.count(level + 1)) {
            for (auto& [childIdx, childVal] : levelNodes[level + 1]) {
                if (childIdx / 2 == index) {
                    isLeaf = false;
                    dfs(childVal, level + 1, childIdx, sum);
                }
            }
        }
        if (isLeaf) ans += sum;
    }

public:
    int pathSum(vector<int>& nums) {
        ans = 0;
        levelNodes.clear();

        for (int x : nums) {
            int val = x % 10; x /= 10;
            int pos = x % 10; x /= 10;
            int level = x;
            int index = (1 << (level - 1)) + pos - 1;
            levelNodes[level].emplace_back(index, val);
        }

        // Root is at level 1, index 1
        dfs(levelNodes[1][0].second, 1, levelNodes[1][0].first, 0);
        return ans;
    }
};

int main() {
    Solution ob;
    vector<int> v = {113, 215, 221};
    cout << ob.pathSum(v); // 12
    return 0;
}

ความซับซ้อน

• เวลา: O(N) – N = จำนวนโหนด (≤ 15 สำหรับ depth 4)
• พื้นที่: O(N)

ข้อสังเกต

• LeetCode 666
• โครงสร้าง Full Binary Tree ทำให้คำนวณ parent-child ได้จาก index แทน pointer
• Depth ≤ 4 → จำนวนโหนดสูงสุด 15 → ใส่ array ขนาดคงที่ได้
• โค้ดต้นฉบับใช้ map> และ (1 << (level-1)) + pos - 1 เหมือนกัน