# Java iterative solution, just keep building pathSums topdown

• ``````class Solution {
public int pathSum(int[] nums) {
// algorithm 2017/08/27: simply build the path from top down in each node without recursion
if (null == nums || 0 == nums.length) {
return 0;
}

// we know the depths, so we just simply calculate the pathSums for each node, from root to leaf
Integer[][] nodeVals = new Integer[5][9];
Integer[][] pathSums = new Integer[5][9];   // 4 depth, at most 8 nodes at the bottom

// map depth/pos => value
for (int num : nums) {
int depth    = num / 100;
int posValue = num % 100;
int pos      = posValue / 10;
int value    = posValue % 10;

nodeVals[depth][pos] = value;
}

// calculate from top down
if (null == nodeVals[1][1]) {
return 0;       // no root?
}

int result = 0;

for (int depth = 1; depth <= 4; depth++) {
int countNodes = 1 << (depth-1);
for (int pos = 1; pos <= countNodes; pos++) {
if (null != nodeVals[depth][pos]) {
if (1 == depth) {
pathSums[1][1] = nodeVals[1][1];    // first level
} else {
int parentDepth = depth - 1;
int parentPos   = (1 == pos % 2) ? (pos+1) /2 : pos/2;
assert null != pathSums[parentDepth][parentPos];        // invalid data?
pathSums[depth][pos] = pathSums[parentDepth][parentPos] + nodeVals[depth][pos];
}

// is this a leaf node?
boolean isLeafNode = false;
if (4 == depth) {
isLeafNode = true;
} else {
int childDepth = depth + 1;
int childPos1  = 2 * pos;
int childPos2  = childPos1 - 1;
if (null == nodeVals[childDepth][childPos1] && null == nodeVals[childDepth][childPos2]) {
isLeafNode = true;
}
}

if (isLeafNode) {
result += pathSums[depth][pos];
}
}
}
}

return result;
}
``````

}

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