highest 2 digits uniquely determines the TreeNode position i.e. (level,pos)

use that as key, lowest 1 digit as value of HashMap tree.

level = num / 10;

pos = num % 10;

To get node's parent, use (level-1, (pos+1)/2)

To get node's left child, use (level+1, pos*2-1), right child (level+1, pos*2)

algorithm

- traverse num[] to construct tree map.
- traverse num[] again and if a leaf is detected, trace back its root while computing the accumulated sum

runtime: assuming it is a balanced binary tree of size n

it has n leaves and therefore n paths made of n*h nodes. h = logn.

so O(nlogn)

```
class Solution {
public int pathSum(int[] nums) {
Map<Integer, Integer> tree = new HashMap<>();
for (int num : nums) {
tree.put(num / 10, num % 10);
}
int sum = 0;
for (int num : nums) {
if (isLeaf(num / 10, tree)) {
sum += getPathSum(num / 10, tree);
}
}
return sum;
}
private boolean isLeaf(int key, Map<Integer, Integer> tree) {
return !tree.containsKey((key / 10 + 1) * 10 + (key % 10) * 2 - 1) && !tree.containsKey((key / 10 + 1) * 10 + (key % 10) * 2);
}
private int getPathSum(int key, Map<Integer, Integer> tree) {
int sum = 0;
do {
sum += tree.get(key);
key = (key / 10 - 1) * 10 + (key % 10 + 1) / 2;
}
while (tree.containsKey(key));
return sum;
}
}
```