666. Path Sum IV

• Difficulty: Medium

• Topics: Tree

• Similar Questions:

  • Path Sum

  • Path Sum II

  • Binary Tree Maximum Path Sum

  • Path Sum III

Problem:

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 tree 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.

Solutions:

class Solution {
public:
    int pathSum(vector<int>& nums) {
        if (nums.size() == 0)   return 0;
        sort(nums.begin(), nums.end());

        int curLevel = 0;
        vector<int> curLevelVals = {0};
        vector<int> lastLevelVals;

        vector<vector<int>> tree;

        for (auto num : nums) {
            int level = num/100;
            int pos = (num - level * 100)/10;
            int val = num % 10;
            if (level != curLevel) {
                tree.push_back(lastLevelVals);
                lastLevelVals = curLevelVals;
                curLevelVals.clear();
                curLevelVals.resize(1 << (level - 1), -1);
                curLevel = level;           
            } 

            {
                curLevelVals[pos-1] = val + lastLevelVals[(pos-1)/2];
            }
        }

        tree.push_back(lastLevelVals); // don't forget to include lastLevelVals
        tree.push_back(curLevelVals);

        int sum = 0;
        for (int level = 0; level < tree.size(); ++level) {
            for (int i = 0; i < tree[level].size(); ++i) {
                if (tree[level][i] != -1 && (level == tree.size() - 1 || tree[level+1][2*i] == -1 && tree[level + 1][2*i + 1] == -1)) { // should also include leaf not at last level
                    sum += tree[level][i];
                }
            }
        }

        return sum;
    }
};