# Java solution using iterative traversal

• The given array "nums" stores the tree nodes in an order of the breadth first search. We may traverse all the tree nodes iteratively using a queue. When the depth of the head of the queue is two levels smaller than current node (parent-child relation requires one level difference), or the positions of the head of the queue and current node do not match the parent-child relation (left_child.pos = 2 * parent.pos, right_child.pos = 2 * parent.pos + 1, if we define the position in the range of [0, 7]), we just remove the head of the queue until the parent of current node is found. The path sum is added level by level down to the leaves. We add up all leaf nodes visited to get the final answer.

``````class Solution {
class TreeNode {
int depth, pos, val;
TreeNode left, right;
public TreeNode(int depth, int pos, int val) {
this.depth = depth;
this.pos = pos;
this.val = val;
}
}
public int pathSum(int[] nums) {
int sum = 0;
for (int num : nums) {
int d = num / 100; // depth
int p = (num - 100 * d) / 10; // position
int v = num - 100 * d - 10 * p; // value
TreeNode node = new TreeNode(d, p - 1, v);
if (!queue.isEmpty()) {
while (!queue.isEmpty() && (queue.peek().depth < d - 1 || queue.peek().pos != (p - 1) / 2)) { // looking for the parent of current TreeNode
TreeNode temp = queue.poll();
if (temp.left == null && temp.right == null) // adding up leaves
sum += temp.val;
}
if (queue.peek().pos * 2 == p - 1)
queue.peek().left = node;
else
queue.peek().right = node;
node.val += queue.peek().val;
}
queue.offer(node);
}
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node.left == null && node.right == null) // adding up leaves
sum += node.val;
}
return sum;
}
}
``````

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