666 Path Sum IV

666. Path Sum IV

1. Question

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

   Dof this node,1 <= D <= 4.

2. The tens digit represents the positionPof 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 valueVof this node,0 <= V <= 9.

Given a list ofascendingthree-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.

2. Implementation

思路：这题给一个数组，数组的每个数是都是三位数，百位数代表在树的第几层，中位数代表数在该层的位置(从1开始算), 而个位数则代表该节点在树里的值。

（1） 题目提到，位置的信息是和full binary tree一样的，这意味着，给定一个node的位置，我们知道它的left children在下一层的位置是node的position * 2 -1(position是从1开始), right children的position则是node的position * 2。

（2）有了以上这些信息后，我们就可以利用一个map, 以数组每个数的前面两位作为key, 最后一位作为value, 放在map里，利用Path Sum同样的思路从根节点(数组第一个数）递归地找出path sum

class Solution {
    public int pathSum(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            int key = num / 10;
            int value = num % 10;
            map.put(key, value);
        }

        int[] sum = new int[1];
        getPathSum(nums[0] / 10, 0, map, sum);
        return sum[0];
    }

    public void getPathSum(int nodeInfo, int curSum, Map<Integer, Integer> map, int[] sum) {
        if (!map.containsKey(nodeInfo)) {
            return;
        }

        int level = nodeInfo / 10;
        int pos = nodeInfo % 10;
        int value = map.get(nodeInfo);

        curSum = curSum + value;

        int left = (level + 1) * 10 + pos * 2 - 1;
        int right = (level + 1) * 10 + pos * 2;

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

        getPathSum(left, curSum, map, sum);
        getPathSum(right, curSum, map, sum);
    }
}

3. Time & Space Complexity

时间空间复杂度都是O(n)