[JAVA] Make tree by array and dfs / T : O(1), S : O(1)


  • 0
    J
    class Solution {
        int sum = 0;
        public int pathSum(int[] nums) {
            int[][] tree = new int[4][8];
            for(int i = 0; i < 4 ; i++)
                Arrays.fill(tree[i], -1);
            
            for(int i = 0; i < nums.length; i++){
                int hund = nums[i] / 100;
                int ten = (nums[i] % 100) / 10;
                int val = nums[i] % 10;
         
                tree[hund-1][ten-1] = val;
            }
            
            getSum(tree, 0, 0);
            return sum;
        }
        
        public int getSum(int[][] tree, int depth, int loc){
            if(depth > 3 || tree[depth][loc] == -1) {
                return 0;
            }
            
            int num_path = getSum(tree, depth+1, 2*loc) + getSum(tree, depth+1, 2*loc+1);
            if(num_path == 0 && tree[depth][loc] != -1){
                sum += tree[depth][loc];
                return 1;
            }
            
            sum += (num_path * tree[depth][loc]);
            return num_path;
        }
    }
    

Log in to reply
 

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