Java DFS Solution using Jagged Array


  • 0
    class Solution {
        int sum = 0;
        public int pathSum(int[] nums) {
            int val = 0;
            int residue = 0;  
            sum = 0;
            int[][] tree = new int[4][];
            tree[0] = new int[1];
            tree[1] = new int[2];
            tree[2] = new int[4];
            tree[3] = new int[8];
            Arrays.fill(tree[0],-1);
            Arrays.fill(tree[1],-1);
            Arrays.fill(tree[2],-1);
            Arrays.fill(tree[3],-1);
            
            for(int i=nums.length-1;i>=0;--i){
                val = nums[i];
                residue = val - val/100*100;
                tree[val/100-1][residue/10-1] = residue%10;
            }        
           
            dfs(tree,0,0);        
            return sum;
        }
        
        public int dfs(int[][] tree,int level,int pos){
            if(level > 3 || tree[level][pos] == -1) return 0;
            int leaves = 0;
            leaves = dfs(tree,level+1,pos<<1) + dfs(tree,level+1,(pos<<1)+1);        
            if(leaves == 0) sum += tree[level][pos];
            else sum += (leaves * tree[level][pos]);        
            return leaves == 0 ? 1 : leaves;
        }
    }
    

Log in to reply
 

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