Java Recursion Without Rebuilding the Tree


  • 0
    K
    private class Pair {
        int sum;
        int leafCount;
        private Pair(int sum, int leafCount) {
            this.sum = sum;
            this.leafCount = leafCount;
        }
    }
    
    public int pathSum(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        return scan(nums, 0).sum;
    }
    
    private Pair scan(int[] nums, int i) {
        if (i == -1)
            return new Pair(0, 0);
        int val = nums[i]%10;
        int lv = nums[i]/100;
        int p = nums[i]/10%10;
        Pair lp = scan(nums, findChild(nums, lv+1, 2*p-1, i));
        Pair rp = scan(nums, findChild(nums, lv+1, 2*p, i));
        int leafCount = Math.max(1, lp.leafCount+rp.leafCount);
        return new Pair(lp.sum+rp.sum+val*leafCount, leafCount); 
    }
    
    private int findChild(int[] nums, int lv, int p, int start) {
        for (int i = start; i < nums.length && nums[i]/100 <= lv; i++) {
            if (nums[i]/100 == lv && nums[i]/10%10 == p)
                return i;
        }
        return -1;
    }

Log in to reply
 

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