Easy Solution using array


  • 0
    W
    public int pathSum(int[] nums) {
        if (nums == null || nums.length == 0) 
              return 0;
        
        Integer[] tree = new Integer[16];
        int level = 0, pos = 0;
        for (int num : nums) {
            level = num/100;
            pos = (1 << (level - 1)) + (num/10)%10 - 1;
            tree[pos] = num%10;
        }
                
        return traverse(tree, 0, 1);
    }
    
    private int traverse(Integer[] tree, int preSum, int pos) {
        if(pos >= tree.length || tree[pos] == null)
            return 0;
        
        int curSum = tree[pos] + preSum;
        // leaf Node
        if(2*pos >= tree.length || (tree[2*pos] == null && tree[2*pos + 1] == null))
            return curSum;
        
        return traverse(tree, curSum, 2*pos) + traverse(tree, curSum, 2*pos + 1);
    }

Log in to reply
 

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