Approach #1: Convert to Tree [Accepted]
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.
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.
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.
- Time and Space Complexity: . The analysis is the same as in Approach #1.
Analysis written by: @awice.