【LintCode题解|阿里巴巴面试真题：路径和 IV】

【题目描述】

如果树的深度小于5，则该树可以由三位整数的列表表示。 对于此列表中的每个整数： 百位数表示该节点的深度D，1 <= D <= 4。 2.十位数表示该节点在其所属级别中的位置P，1 <= P <= 8.该位置与完整二叉树中的位置相同。 3.单位数字表示该节点的值V，0 <= V <= 9。 给定一个表示深度小于5的二叉树的升序三位整数列表，您需要返回从根到叶子的所有路径和的总和。

【题目样例 】

例 1: 输入: [113, 215, 221] 输出: 12 解释: 该树如下图所示: 3 / 5 1 所有的路径和为 (3 + 5) + (3 + 1) = 12. 例 2: 输入: [113, 221] 输出: 4 解释: 该树如下所示: 3 1 所有的路径和为 (3 + 1) = 4.

【题目解析 （Python）】

先将每个数的前两位取出，还原其在二叉树对应数组的位置，将其值放入对应数组的位置中。再按深度搜索的方法计算所有路径的和，并相加得出结果。

【具体解析详见九章参考程序】

https://www.jiuzhang.com/solution/path-sum-iv/?utm_source=sc-jianshu-fks