If the depth of a tree is smaller than
5, then this tree can be represented by a list of three-digits integers.
For each integer in this list:
Dof this node,
1 <= D <= 4.
Pof this node in the level it belongs to,
1 <= P <= 8. The position is the same as that in a full binary tree.
Vof this node,
0 <= V <= 9.
Given a list of
ascending three-digits integers representing a binary with the depth smaller than 5. You need to return the sum of all paths from the root towards the leaves.
Input: [113, 215, 221] Output: 12 Explanation: The tree that the list represents is: 3 / \ 5 1 The path sum is (3 + 5) + (3 + 1) = 12.
Input: [113, 221] Output: 4 Explanation: The tree that the list represents is: 3 \ 1 The path sum is (3 + 1) = 4.
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.\n
There are two steps, the tree construction, and the traversal.\n
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.\n
Intuition and Algorithm\n
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.
Analysis written by: @awice.\n