Java DFS, with explanation


  • 0

    Find the left child and right child based on the first two digits;

    [abc] 's left child = [(a+1)(b*2-1)(...)]

    [abc]'s right child = [(a+1)(b*2)(...)]

    dfs, when current node is a leaf, add the sum of path to totalSum

    class Solution {
        
        int totalSum;
        public int pathSum(int[] nums) {
            if (nums == null || nums.length == 0) return 0;
            totalSum = 0;
            dfs(nums, 0, 0);
            return totalSum;
        }
        
        private void dfs(int[] nums, int i, int sum){
            int n = nums[i];
            int v = n%10; //value
            int idx = (n/10)%10; //index
            int d = n/100; //depth
            sum += v;
            int left = (d+1)*10+idx*2-1; //left child's depth and index
            int right = (d+1)*10+idx*2; //right child's depth and index
            boolean foundLeft = false, foundRight = false;
            for(int j = i+1; j<nums.length; j++){
                int tmp = nums[j]/10;
                if (tmp > right) break;
                if (tmp == left) {
                    foundLeft = true;
                    dfs(nums, j, sum);
                }
                if (tmp == right) {
                    foundRight = true;
                    dfs(nums, j, sum);
                }
            }
            if (!foundLeft && !foundRight) 
                totalSum+=sum; //if is leaf, add the sum of the path to total sum;
        }
    }
    

Log in to reply
 

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