# Java solution, Represent tree using HashMap

• How do we solve problem like this if we were given a normal tree? Yes, traverse it, keep a root to leaf running sum. If we see a leaf node (node.left == null && node.right == null), we add the running sum to the final result.

Now each tree node is represented by a number. 1st digits is the `level`, 2nd is the `position` in that `level` (note that it starts from `1` instead of `0`). 3rd digit is the value. We need to find a way to traverse this `tree` and get the sum.

The idea is, we can form a `tree` using a HashMap. The `key` is first two digits which marks the position of a node in the tree. The `value` is value of that node. Thus, we can easily find a node's left and right children using math.
Formula: For node `xy?` its left child is `(x+1)(y*2-1)?` and right child is `(x+1)(y*2)?`

Given above HashMap and formula, we can traverse the `tree`. Problem is solved!

``````class Solution {
int sum = 0;
Map<Integer, Integer> tree = new HashMap<>();

public int pathSum(int[] nums) {
if (nums == null || nums.length == 0) return 0;

for (int num : nums) {
int key = num / 10;
int value = num % 10;
tree.put(key, value);
}

traverse(nums[0] / 10, 0);

return sum;
}

private void traverse(int root, int preSum) {
int level = root / 10;
int pos = root % 10;
int left = (level + 1) * 10 + pos * 2 - 1;
int right = (level + 1) * 10 + pos * 2;

int curSum = preSum + tree.get(root);

if (!tree.containsKey(left) && !tree.containsKey(right)) {
sum += curSum;
return;
}

if (tree.containsKey(left)) traverse(left, curSum);
if (tree.containsKey(right)) traverse(right, curSum);
}
}
``````

• @shawngao: Editorial level explanation, thank you!

• Similar idea, but using an integer matrix rather than HashMap:

``````class Solution {
public int pathSum(int[] nums) {
Integer[][] matrix = new Integer[4 + 1][8 + 1];
for (int num : nums) {
int[] node = parseElement(num);
matrix[node[0]][node[1]] = node[2];
}
matrix[0][0] = 0;
matrix[0][1] = 0;
helper(matrix, 1, 1);
return matrix[0][0];
}

public void helper(Integer[][] matrix, int i, int j) {
if (matrix[i][j] == null)
return;
int base = 2 * (j - 1);
matrix[0][1] += matrix[i][j];
if (i == 4 || (matrix[i + 1][base + 1] == null && matrix[i + 1][base + 2] == null)) {
matrix[0][0] += matrix[0][1];
} else {
helper(matrix, i + 1, base + 1);
helper(matrix, i + 1, base + 2);
}
matrix[0][1] -= matrix[i][j];
}

public int[] parseElement(int num) {
int[] res = new int[3];
for (int i = 0; i < 3; i++) {
res[2 - i] = num % 10;
num /= 10;
}
return res;
}
}
``````

• no need to keep the global sum

``````class Solution {
public:
int pathSum(vector<int>& nums) {
if (nums.size() == 0) return 0;
unordered_map<int, int> tree;
for (int num : nums) {
tree[num / 10] = num % 10;
}
return pathSum(tree, 0, nums[0] / 10);
}

int pathSum(unordered_map<int, int> &tree, int prevSum, int curr) {
if (!tree.count(curr)) return 0;
int level = curr / 10, pos = curr % 10, val = tree[curr];
int left = (level + 1) * 10 + 2 * pos - 1;
int right = (level + 1) * 10 + 2 * pos;

int currSum = prevSum + val;
if (!tree.count(left) && !tree.count(right)) return currSum;
return pathSum(tree, currSum, left) + pathSum(tree, currSum, right);

}
};
``````

• ONE PASS.

``````        int[][] map = new int[5][9];
int ans = 0;
for (int num : nums) {
int r = num / 100, c = num % 100 / 10, v = num % 10;
map[r][c] = v;
if (r > 1) {
int p = map[r - 1][(c + 1) / 2];
map[r][c] += Math.abs(p);
if (p > 0) {
ans -= p;
map[r - 1][(c + 1) / 2] = -p;
}
}
ans += map[r][c];
}
return ans;
``````

• share my solution by traversing the tree "iteratively"

``````class Solution {
public int pathSum(int[] nums) {
//corner
if (nums.length == 0) {
return 0;
}

//store the node(represent by level and col #) and its corresponding path sum which is the sum of path from root to this node
Map<Integer, Integer> map = new HashMap<>();
int sum = 0;
for (int num : nums) {
int level = num/100;
int value = num%10;
int key = (num - value)/10;
int col = (num%100 - value)/10;

if (level == 1) {
map.put(11, value);
} else {
int upperKey = (level-1) * 10 + (col + 1)/2;
map.put(key, value + map.get(upperKey));
}
}

//if the node has no children, then add the path sum
for (int key : map.keySet()) {
int level = key/10;
int col = key%10;

int left = 10* (level+1) + col * 2 - 1;
int right = 10* (level+1) + col * 2 ;
if (!map.containsKey(left) && !map.containsKey(right)) {
sum += map.get(key);
}
}

return sum;
}
}
``````

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