666. Path Sum IV


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:

  1. The hundreds digit represents the depth D of this node, 1 <= D <= 4.
  2. The tens digit represents the position P of this node in the level it belongs to, 1 <= P <= 8. The position is the same as that in a full binary tree.
  3. The units digit represents the value V of 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.

Example 1:

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.

Example 2:

Input: [113, 221]
Output: 4
Explanation: 
The tree that the list represents is: 
    3
     \
      1

The path sum is (3 + 1) = 4.


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.

Submit Solution