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:

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

아니면 두 갈래 나무의 경로의 합이지만 나무의 저장 방식이 바뀌었다. 세 자리의 숫자로 저장하면 백 자리는 이 결점의 깊이, 열 자리는 이 결점이 어느 층에 있는 위치, 한 자리는 이 결점의 값이다.
Python:

class Solution(object):
    def pathSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        class Node(object):
            def __init__(self, num):
                self.level = num/100 - 1
                self.i = (num%100)/10 - 1
                self.val = num%10
                self.leaf = True
                
            def isParent(self, other):
                return self.level == other.level-1 and \
                       self.i == other.i/2

        if not nums:
            return 0
        result = 0
        q = collections.deque()
        dummy = Node(10)
        parent = dummy
        for num in nums:
            child = Node(num)
            while not parent.isParent(child):
                result += parent.val if parent.leaf else 0
                parent = q.popleft()
            parent.leaf = False
            child.val += parent.val
            q.append(child)
        while q:
            result += q.pop().val
        return result

C++:

class Solution {
public:
    int pathSum(vector& nums) {
        if (nums.empty()) return 0;
        int res = 0;
        unordered_map m;
        for (int num : nums) {
            m[num / 10] = num % 10;
        }
        helper(nums[0] / 10, m, 0, res);
        return res;
    }
    void helper(int num, unordered_map& m, int cur, int& res) {
        int level = num / 10, pos = num % 10;
        int left = (level + 1) * 10 + 2 * pos - 1, right = left + 1;
        cur += m[num];
        if (!m.count(left) && !m.count(right)) {
            res += cur;
            return;
        }
        if (m.count(left)) helper(left, m, cur, res);
        if (m.count(right)) helper(right, m, cur, res);
    }
};

　　
유사한 제목:
[LeetCode] 112. Path Sum 경로 및
[LeetCode] 113. Path Sum II 경로 및 II
[LeetCode] 437. Path Sum III 경로 및 III
 

All LeetCode Questions List 제목 요약

　　
 
다음으로 전송:https://www.cnblogs.com/lightwindy/p/8606825.html