Formatted question description: https://leetcode.ca/all/666.html

666. Path Sum IV (Medium)

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.

Companies:
Alibaba

Related Topics:
Tree

Similar Questions:

Solution 1.

// OJ: https://leetcode.com/problems/path-sum-iv/

// Time: O(N)
// Space: O(N)
class Solution {
public:
    int pathSum(vector<int>& nums) {
        unordered_map<int, int> m;
        for (int n : nums) {
            m[n / 10] = n % 10;
        }
        int sum = 0;
        for (int n : nums) {
            int d = n / 100, p = n / 10 % 10, v = m[d * 10 + p];
            int left = (d + 1) * 10 + p * 2 - 1, right = left + 1;
            if (m.find(left) != m.end()) m[left] += v;
            if (m.find(right) != m.end()) m[right] += v;
            if (m.find(left) == m.end() && m.find(right) == m.end()) sum += v;
        }
        return sum;
    }
};

Java

class Solution {
    public int pathSum(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        Map<Integer, Integer> depthPositionValueMap = new HashMap<Integer, Integer>();
        for (int num : nums) {
            int depthPosition = num / 10, value = num % 10;
            depthPositionValueMap.put(depthPosition, value);
        }
        Queue<int[]> queue = new LinkedList<int[]>();
        int num0 = nums[0];
        queue.offer(new int[]{num0 / 10, num0 % 10});
        int sum = 0;
        while (!queue.isEmpty()) {
            int[] depthPositionValue = queue.poll();
            int depthPosition = depthPositionValue[0], value = depthPositionValue[1];
            int depth = depthPosition / 10, position = depthPosition % 10;
            int leftDepthPosition = (depth + 1) * 10 + position * 2 - 1, rightDepthPosition = (depth + 1) * 10 + position * 2;
            int left = depthPositionValueMap.getOrDefault(leftDepthPosition, -1), right = depthPositionValueMap.getOrDefault(rightDepthPosition, -1);
            if (left < 0 && right < 0)
                sum += value;
            else {
                if (left >= 0) {
                    int leftValue = left % 10;
                    queue.offer(new int[]{leftDepthPosition, value + leftValue});
                } if (right >= 0) {
                    int rightValue = right % 10;
                    queue.offer(new int[]{rightDepthPosition, value + rightValue});
                }
            }
        }
        return sum;
    }
}

All Problems

All Solutions