# Java DFS, with explanation

• 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);
}

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;
}
}
``````

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