# Java bottom-up recursive O(n) space O(nlogn) time

• 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, pos2-1), right child (level+1, pos2)

algorithm

1. traverse num[] to construct tree map.
2. 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;
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.