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 depth-first 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 depth-first search.


Approach #2: Direct Traversal [Accepted]

Intuition and Algorithm

As in Approach #1, we will depth-first search on the tree. One time-saving 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.