[LintCode] Problem 863 - Binary Tree Path Sum IV

Posted on | In ,

If the depth of a tree is smaller than 5, 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

No.1

Input: [113, 215, 221]

Output: 12

Explanation:
The tree that the list represents is:

1
2
3
  3
 / \
5   1

The path sum is (3 + 5) + (3 + 1) = 12.

No.2

Input: [113, 221]

Output: 4

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
private int sum = 0;

public int pathSum(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();

    for (int num : nums)
        map.put(num / 10, num % 10);

    traverse(nums[0] / 10, map, 0);
    return sum;
}

private void traverse(int root, Map<Integer, Integer> map, int prevSum) {
    int level = root / 10;
    int pos = root % 10;
    int left = (level + 1) * 10 + pos * 2 - 1;
    int right = (level + 1) * 10 + pos * 2;

    int curSum = prevSum + map.get(root);

    if (!map.containsKey(left) && !map.containsKey(right)) {
        sum += curSum;
        return;
    }

    if (map.containsKey(left))
        traverse(left, map, curSum);

    if (map.containsKey(right))
        traverse(right, map, curSum);
}