Approach #1: Convert to Tree [Accepted]
Intuition
Convert the given array into a tree using Node objects. Afterwards, for each path from root to leaf, we can add the sum of that path to our answer.
Algorithm
There are two steps, the tree construction, and the traversal.
In the tree construction, we have some depth, position, and value, and we want to know where the new node goes. With some effort, we can see the relevant condition for whether a node should be left or right is pos  1 < 2**(depth  2)
. For example, when depth = 4
, the positions are 1, 2, 3, 4, 5, 6, 7, 8
, and it's left when pos <= 4
.
In the traversal, we perform a depthfirst search from root to leaf, keeping track of the current sum along the path we have travelled. Every time we reach a leaf (node.left == null && node.right == null)
, we have to add that running sum to our answer.
Complexity Analysis

Time Complexity: where is the length of
nums
. We construct the graph and traverse it in this time. 
Space Complexity: , the size of the implicit call stack in our depthfirst search.
Approach #2: Direct Traversal [Accepted]
Intuition and Algorithm
As in Approach #1, we will depthfirst search on the tree. One timesaving idea is that we can use num / 10 = 10 * depth + pos
as a unique identifier for that node. The left child of such a node would have identifier 10 * (depth + 1) + 2 * pos  1
, and the right child would be one greater.
Complexity Analysis
 Time and Space Complexity: . The analysis is the same as in Approach #1.
Analysis written by: @awice.