# 666. Path Sum IV 路径总和 IV

@TOC

## # 题目描述

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.
``````

## # 解题方法

### # DFS

C++代码如下：

``````class Solution {
public:
int pathSum(vector<int>& nums) {
vector<int> tree(64, -1);
for (int n : nums) {
int v = n % 10; n /= 10;
int p = n % 10; n /= 10;
int d = n % 10;
tree[(int)pow(2, d - 1) + p - 1] = v;
}
dfs(tree, 1, 0);
return sum;
}
void dfs(vector<int>& tree, int index, int parent) {
if (tree[index] == -1) return;
if (tree[index * 2] == -1 && tree[index * 2 + 1] == -1) {
sum += parent + tree[index];
return;
}
dfs(tree, index * 2, parent + tree[index]);
dfs(tree, index * 2 + 1, parent + tree[index]);
}
private:
int sum = 0;
};
``````

## # 日期

2019 年 9 月 24 日 —— 梦见回到了小学，小学已经芳草萋萋破败不堪