[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