[lintcode] problem 863 – binary tree path sum iv

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:

The hundreds digit represents the depth D of this node, 1 <= D <= 4.
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.
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

private int sum = 0;

public int (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);
}

[lintcode] problem 863 – binary tree path sum iv

Example

No.1

No.2

Code

近期文章

近期评论

标签

热门

文章归档

分类目录

功能