PathSumIV [source code]

public class PathSumIV {
static
/******************************************************************************/
class Solution {
    public int pathSum(int[] nums) {
        Integer[][] matrix = new Integer[4 + 1][8 + 1];
        for (int num : nums) {
            int[] node = parseElement(num);
            matrix[node[0]][node[1]] = node[2];
        }
        matrix[0][0] = 0;
        matrix[0][1] = 0;
        helper(matrix, 1, 1);
        return matrix[0][0];
    }

    public void helper(Integer[][] matrix, int i, int j) {
        if (matrix[i][j] == null)
            return;
        int base = 2 * (j - 1);
        matrix[0][1] += matrix[i][j];
        if (i == 4 || (matrix[i + 1][base + 1] == null && matrix[i + 1][base + 2] == null)) {
            matrix[0][0] += matrix[0][1];
        } else {
            helper(matrix, i + 1, base + 1);
            helper(matrix, i + 1, base + 2);
        }
        matrix[0][1] -= matrix[i][j];
    }

    public int[] parseElement(int num) {
        int[] res = new int[3];
        for (int i = 0; i < 3; i++) {
            res[2 - i] = num % 10;
            num /= 10;
        }
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        PathSumIV.Solution tester = new PathSumIV.Solution();
        int[][] inputs = {
            {113,215,221}, {12},
            {111,217,221,315,415}, {20},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            int[] nums = inputs[2 * i];
            int ans = inputs[1 + 2 * i][0];
            System.out.println(Printer.separator());
            int output = tester.pathSum(nums);
            System.out.println(
                Printer.wrapColor(Printer.array(nums), "magenta") +
                " -> " + output +
                Printer.wrapColor(", expected: " + ans, ans == output ? "green" : "red")
                );
        }
    }
}

首先题目条件里说这里给的这个list是ascending, 是什么意思? 因为这个题目给的数字都是三位数, 所以sort的时候实际上最后比较的就是头两位; 加上这里的定义, 第一位是depth, 第二位是level里面的位置, 所以最后ascending对应的order其实就是一个从上到下, 从左到右的BFS的顺序; 当然, 这个信息未必在这个题目里面是最关键的信息, 但是做一个题目, 先把题目本身读懂, 这个要求还是不过分的;

我本来的想法是直接先用一个matrix来记录所有的node, 这样做到一个类似hashing的sort的作用; 不过如果我们已经知道了这些node给出的order, 那么这个过程还有必要吗? 当然, 想到这个过程来完成一个类似sort的操作(来确定一个order), 这个并不是一个错误的想法;

这个题目的另外一个难点, 就是这个tree可能是不完整的; 这里他的定义的第二条, 说明P是在一个full tree里面的位置, 其实就有点类似LeetCode的OJ的时候, 那种用Null来占位的表示方法; 要考虑某些level可能不完整的话, 逻辑的构造就又难了一点了; 为了处理这个uncertainty, 一个思路就是relaxation: full tree好做, 那我们就先按照full的来做, 再考虑能不能扩展到做一般性的情况; 大部分时候都是可以扩展的, 少数时候真的不能扩展, 一般也能感觉的出来;

一种思路是可以在计算的时候假设不存在的那些Null的branch其实是有node的, 全都是0而已; 这样好像好计算一些? //好像这种每次出现一个node就直接向leaf level沉降的算法不是特别好用; 因为最后实际的tree的leaf可能并不在最底下那一层; 这个算法最后最大的问题, 还是没有理解path sum问题的一个关键点: 每一个path sum只有当碰到一个leaf的时候才能收尾; 问题就在于不知道leaf在哪里;

其实我现在在思考的这些个方法都属于有点优化的方法了, 这个问题要说最简单的方法, 直接就是把这个tree给build出来就行了; 当然, 并不是一个真正的BST, 而是一个matrix里面build出来, 然后用BFS的方法来走就行了; 上面那些优化办法想了半天, 其实也没有想通, 最后想想干脆还是用这个笨办法来做好了; 沉降思路的代码可以自己去LeetCode的submission里面看历史记录;

本来的想法是matrix build出来之后用BFS的方法来做, 不过BFS做path sum好像不是特别的好, 最后想了想还是干脆用DFS的思路来做;

顺便再次提醒一下, java里面land和lor的优先级是一个DNF的结构:

java> false && false || true  
java.lang.Boolean res4 = true

大概明确思路之后, 这个题目还是比较简单的做出来了; 最后的速度是15ms (N/A);

说是简单, 其实也是花了不少时间; 这个题目的难点在于, 要能够理解一个在matrix里面表达的BST; 同时, 在这样一个matrix里面, 你的left link和right link怎么表达, 怎么寻找, 也要处理好; 如果把这两个概念想清楚了, 这个题目本身应该是不难的, 主要还是我自己对于helper的这个recursion写法还不够熟练, 最后花了很多时间debug;

另外, 看discussion里面的时候, 发现我现在对于Empty Case的判断又有点生疏了. 感觉还是Premature Optmization在作怪: 见过很多算法最后实际上因为算法本身的特性导致不需要专门的处理Empty Case, 所以最后现在很多时候算法一个字都还没有写, 脑子里就先开始潜意识里希望这个算法也不需要处理Empty Case就好了; 事实上, 你看的面经多你也知道的, 你这个Empty case写了, 顶多是你多了一点redundancy, 但是如果你没写,, 最后很可能面试官就因为这个不让你过了, 你自己选嘛, offer还是装逼;

discussion最优解:

@shawngao said in Java solution, Represent tree using HashMap:

How do we solve problem like this if we were given a normal tree? Yes, traverse it, keep a root to leaf running sum. If we see a leaf node (node.left == null && node.right == null), we add the running sum to the final result.

Now each tree node is represented by a number. 1st digits is the level, 2nd is the position in that level (note that it starts from 1 instead of 0). 3rd digit is the value. We need to find a way to traverse this tree and get the sum.

The idea is, we can form a tree using a HashMap. The key is first two digits which marks the position of a node in the tree. The value is value of that node. Thus, we can easily find a node's left and right children using math.
Formula: For node xy? its left child is (x+1)(y*2-1)? and right child is (x+1)(y*2)?

Given above HashMap and formula, we can traverse the tree. Problem is solved!

class Solution {  
    int sum = 0;  
    Map<Integer, Integer> tree = new HashMap<>();  

    public int pathSum(int[] nums) {  
        if (nums == null || nums.length == 0) return 0;  

        for (int num : nums) {  
            int key = num / 10;  
            int value = num % 10;  
            tree.put(key, value);  
        }  

        traverse(nums[0] / 10, 0);  

        return sum;  
    }  

    private void traverse(int root, int preSum) {  
        int level = root / 10;  
        int pos = root % 10;  
        int left = (level + 1) * 10 + pos * 2 - 1;  
        int right = (level + 1) * 10 + pos * 2;  

        int curSum = preSum + tree.get(root);  

        if (!tree.containsKey(left) && !tree.containsKey(right)) {  
            sum += curSum;  
            return;  
        }  

        if (tree.containsKey(left)) traverse(left, curSum);  
        if (tree.containsKey(right)) traverse(right, curSum);  
    }  
}

思路其实是差不多的, 不过他用HashMap来表达这个tree; 这个其实也是自然的, 不过我认为不如我这里这个方法更加的优秀, 因为你看他最后还是要计算left and right child的坐标, 然后查表, 这个计算的核心还是基于查表, 所以不如用我这个表格的方法来做了; 当然, 空间复杂度肯定是他这个好一点;

这个是discussion另外一个最优解:

class Solution {  
    public int pathSum(int[] nums) {  
        int[][] m = new int[5][8];  
        for (int n : nums) {  
            int i = n / 100; // i is 1 based index;  
            int j = (n % 100) / 10 - 1; // j used 0 based index;  
            int v = n % 10;  
            m[i][j] = m[i - 1][j / 2] + v;  
        }  

        int sum = 0;  
        for (int i = 1; i < 5; i++) {  
            for (int j = 0; j < 8; j++) {  
                if (i == 4 || m[i][j] != 0 && m[i + 1][j * 2] == 0 && m[i + 1][j * 2 + 1] == 0){  
                    sum += m[i][j];  
                }  
            }  
        }  
        return sum;          
    }  
}

我本来以为这个题目是没有办法用BFS来做的, 不过这里看来人家还是做到了; 这里他用的一个思路跟我当时的一个想法非常类似, 就是将每一个level的entry向下沉降; 沉降之后, 直接用BFS的思路来找到所有的leaf, 然后加起来就行了; 注意他这里BFS用在了两个地方, 一个是开始build的时候的沉降的过程, 这里的这个沉降其实是一个BFS的过程, 另外一个就是第二个循环这个collect的过程, 不过这个过程里面的这个BFS不是非常关键, 这里只是一个单纯的遍历: Generate&Test而已, 所以order在这里并不是最主要的;

另外一个问题是, 我们说到沉降, 沉降的本质到底是什么? 其实是每两个相邻的level, 下一个level的entry要多加上上一个level里面, 自己的parent, 那么自己的parent这个怎么决定? 他这里的做法是:

m[i][j] = m[i - 1][j / 2] + v;

这个要是我自己想也未必说就想不到, 不过确实没有往这个方向去想; 另外, 这个沉降思路, 或许是一个可以扩展到很多类path sum问题当中的做法;

这个题目还是太新了, discussion暂时还没有更好的解法, 先就这样了;

Problem Description

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.

Difficulty:Medium
Total Accepted:1.4K
Total Submissions:3.1K
Contributor: huihuixd
Companies
alibaba
Related Topics
tree
Similar Questions
Path Sum Path Sum II Binary Tree Maximum Path Sum Path Sum III