题目描述：

LeetCode 666. Path Sum IV

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.

题目大意：

给定深度不超过5的二叉树，用三位数xyz表示节点（x表示深度，y表示在某层的位置，z表示节点的值）。

求从根节点到每一个叶子节点的路径之和

解题思路：

假设某节点前两位数为xy，则其父亲节点前两位数为(x - 1) * 10 + (y + 1) / 2

Python代码：

class Solution(object):
    def pathSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dmap = {1 : 0}
        leaves = set([1])
        for num in nums:
            path, val = num / 10, num % 10
            lvl, seq = path / 10, path % 10
            parent = (lvl - 1) * 10 + (seq + 1) / 2
            dmap[path] = dmap[parent] + val
            leaves.add(path)
            if parent in leaves: leaves.remove(parent)
        return sum(dmap[v] for v in leaves)

 

本文链接：http://bookshadow.com/weblog/2017/08/30/leetcode-path-sum-iv/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码