Fastest Java Solution with no global variables and limited space.


  • 0
    S

    The logic is to represent the tree as a map.
    So let's suppose the numbers are: [111, 217, 221, 315, 415]. The map will represent this as:
    11 -> 1
    21 -> 7
    22 -> 1
    31 -> 5
    41 -> 5

    After this we traverse the array again from the last element to see if it has any child nodes. If yes then it is not a leaf, move on to next. If it has no child nodes, start storing the node value while traversing above to the root node.

    Let me know if you need more explanation :)

    class Solution {
        public int pathSum(int[] nums) {
    	if(nums == null || nums.length == 0 || nums[0] == 0) return 0;
    	Map<Integer, Integer> path = new HashMap<>();
    
    	for(int n: nums) {
    	    path.put(n / 10, n % 10);
    	}
    
    	int curValue = 0;
    	int nextLeft = 0;
    	int nextRight = 0;
    	int sum = 0;
    
    	for(int i = nums.length - 1; i >= 0; --i) {
    	    curValue = nums[i];
    	    nextRight = (curValue / 100 + 1) * 10 + ((curValue / 10) % 10) * 2;
    	    nextLeft = nextRight - 1;
    
    	    if(!path.containsKey(nextRight) && !path.containsKey(nextLeft)) {
    		curValue /= 10;
    		while(curValue >= 11) {
    		    sum += path.get(curValue);
    		    curValue = (curValue / 10 - 1) * 10 + ((curValue % 10) - 1) / 2 + 1;
    		}
                }
            }
            return sum;
        }
    }
    

Log in to reply
 

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