Tổng đường dẫn IV trong C++

Giới thiệu

Cho danh sách số nguyên 3 chữ số đại diện cho cây nhị phân độ sâu < 5. Mỗi số: hàng trăm = độ sâu D (1-4), hàng chục = vị trí P (1-8, như cây đầy đủ), hàng đơn vị = giá trị V (0-9). Tính tổng tất cả đường đi từ gốc đến lá.

Thuật toán: Xây dựng cây + DFS

1. Phân tích từng số: level = x/100, pos = (x/10)%10, val = x%10.
2. Tính index duy nhất cho nút: index = (1 << (level-1)) + pos - 1 (heap indexing).
3. Lưu graph[level].push_back({index, val}).
4. DFS từ gốc (level 1), cộng dồn tổng. Khi gặp lá (không có con ở level+1), cộng vào kết quả.

Cài đặt C++

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

class Solution {
    int ans = 0;
    map<int, vector<pair<int,int>>> graph; // level -> list of (index, val)
    void dfs(int nodeVal, int level, int pos, int sum) {
        bool isLeaf = true;
        for (auto& [idx, val] : graph[level+1]) {
            if (idx / 2 == pos) { // con của nút hiện tại
                isLeaf = false;
                dfs(val, level+1, idx, sum + nodeVal);
            }
        }
        if (isLeaf) ans += sum + nodeVal;
    }
public:
    int pathSum(vector<int>& nums) {
        ans = 0;
        graph.clear();
        for (int x : nums) {
            int val = x % 10;
            x /= 10;
            int pos = x % 10;
            x /= 10;
            int level = x;
            int idx = (1 << (level-1)) + pos - 1;
            graph[level].push_back({idx, val});
        }
        if (!graph[1].empty()) dfs(graph[1][0].second, 1, graph[1][0].first, 0);
        return ans;
    }
};

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

Giải thích ví dụ

113: level=1, pos=1, val=3 (gốc).
215: level=2, pos=1, val=5 (con trái).
221: level=2, pos=2, val=1 (con phải).

Đường đi: 3→5 (sum=8), 3→1 (sum=4). Tổng = 12.

Độ phức tạp

• Thời gian: O(N) – N = số nút (≤ 15).
• Không gian: O(N).

LeetCode 666 "Path Sum IV".