[leetcode/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.

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

源代码

public class Solution {
    /**
     * @param nums: the list
     * @return: the sum of all paths from the root towards the leaves
     */
    class Pair {
        int pathSum;
        int index;

        Pair(int pathSum, int index) {
            this.pathSum = pathSum;
            this.index = index;
        }
    }

    public int pathSumIV(int[] nums) {
        int[] nodes = new int[16];
        Arrays.fill(nodes, -1);
        for (int num : nums) {
            int units = num % 10;
            int tens = num / 10 % 10;
            int hundreds = num / 100 % 10;
            int index = (int) Math.pow(2, hundreds - 1) + (tens - 1);
            nodes[index] = units;
        }
        Pair root = new Pair(nodes[1], 1);
        Stack<Pair> stack = new Stack<>();
        stack.push(root);
        int sum = 0;
        while (!stack.isEmpty()) {
            Pair node = stack.pop();
            int index = node.index;
                        // Reach a leaf node. This path ends.
            if ((index * 2 >= 16 && index * 2 + 1 >= 16) || (nodes[index * 2] == -1 && nodes[index * 2 + 1] == -1)) {
                sum += node.pathSum;
            }
            if (index * 2 < 16 && nodes[index * 2] != -1) {
                stack.push(new Pair(node.pathSum + nodes[index * 2],
                        index * 2));
            }
            if (index * 2 + 1 < 16 && nodes[index * 2 + 1] != -1) {
                stack.push(new Pair(node.pathSum + nodes[index * 2 + 1],
                        index * 2 + 1));
            }
        }
        return sum;
    }
}

更多题解参考：九章官网solution