> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/tree/666.-path-sum-iv.md).

# 666. Path Sum IV

If the depth of a tree is smaller than `5`, then this tree can be represented by a list of three-digits integers.

For each integer in this list:

1. The hundreds digit represents the depth `D` of this node, `1 <= D <= 4.`
2. The tens digit represents the position `P` of this node in the level it belongs to, `1 <= P <= 8`. The position is the same as that in a full binary tree.
3. The units digit represents the value `V` of this node, `0 <= V <= 9.`

Given a list of `ascending` three-digits integers representing a binary tree with the depth smaller than 5, you need to return the sum of all paths from the root towards the leaves.

**Example 1:**

```
Input: [113, 215, 221]
Output: 12
Explanation: 
The tree that the list represents is:
    3
   / \
  5   1

The path sum is (3 + 5) + (3 + 1) = 12.
```

**Example 2:**

```
Input: [113, 221]
Output: 4
Explanation: 
The tree that the list represents is: 
    3
     \
      1

The path sum is (3 + 1) = 4.
```

```cpp
void helper(int root, int curSum, int& res, unordered_map<int, int>& tree) {
    int level = root / 10, pos = root % 10;
    int left = (level + 1) * 10 + pos * 2 - 1, right = (level + 1) * 10 + pos * 2;
    curSum += tree[root];
    if (!tree.count(left) && !tree.count(right)) {
        res += curSum;
        return;
    }
    if (tree.count(left)) helper(left, curSum, res, tree);
    if (tree.count(right)) helper(right, curSum, res, tree);
    
}
int pathSum(vector<int>& nums) { // time: O(n); space: O(n)
    if (nums.empty()) return 0;
    unordered_map<int, int> tree; // <DP, V>
    for (int num : nums) {
        int key = num / 10, value = num % 10;
        tree[key] = value;
    }
    int res = 0;
    helper(nums[0] / 10, 0, res, tree);
    return res;
}
```