Java iterative solution, just keep building pathSums topdown


  • 0
    A
    class Solution {
    public int pathSum(int[] nums) {
        // algorithm 2017/08/27: simply build the path from top down in each node without recursion
        if (null == nums || 0 == nums.length) {
            return 0;
        }
        
        // we know the depths, so we just simply calculate the pathSums for each node, from root to leaf
        Integer[][] nodeVals = new Integer[5][9];
        Integer[][] pathSums = new Integer[5][9];   // 4 depth, at most 8 nodes at the bottom
        
        // map depth/pos => value
        for (int num : nums) {
            int depth    = num / 100;
            int posValue = num % 100;
            int pos      = posValue / 10;
            int value    = posValue % 10;
            
            nodeVals[depth][pos] = value;
        }
        
        // calculate from top down
        if (null == nodeVals[1][1]) {
            return 0;       // no root?
        }
        
        int result = 0;
        
        for (int depth = 1; depth <= 4; depth++) {
            int countNodes = 1 << (depth-1);
            for (int pos = 1; pos <= countNodes; pos++) {
                if (null != nodeVals[depth][pos]) {
                    if (1 == depth) {
                        pathSums[1][1] = nodeVals[1][1];    // first level
                    } else {
                        int parentDepth = depth - 1;
                        int parentPos   = (1 == pos % 2) ? (pos+1) /2 : pos/2;
                        assert null != pathSums[parentDepth][parentPos];        // invalid data?
                        pathSums[depth][pos] = pathSums[parentDepth][parentPos] + nodeVals[depth][pos];
                    }
                    
                    // is this a leaf node?
                    boolean isLeafNode = false;
                    if (4 == depth) {
                        isLeafNode = true;
                    } else {
                        int childDepth = depth + 1;
                        int childPos1  = 2 * pos;
                        int childPos2  = childPos1 - 1;
                        if (null == nodeVals[childDepth][childPos1] && null == nodeVals[childDepth][childPos2]) {
                            isLeafNode = true;
                        }
                    }
                    
                    if (isLeafNode) {
                        result += pathSums[depth][pos];
                    }
                }
            }
        }
        
        return result;        
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.