Beats 100% of other Java solutions. Easy-to-understand explanation.


  • 0
    G
    public class Solution {
        int count = 0;
        public int pathSum(TreeNode root, int sum) {
            if(root == null) return 0;
            int depth = findDepth(root);
            int[] pathArray = new int[depth];
            helper(root, sum, pathArray, 0, depth);
            return count;
        }
    
     public void helper(TreeNode root, int total, int[] nums, int level, int depth) {
            if(root == null) return; 
            if(level >= depth) return;
            nums[level] = root.val;
            int sum = 0;
            for(int i = level; i>=0; i--) {
                sum += nums[i];
                if(sum == total)
                    count++;
            }
            helper(root.left, total, nums, level + 1, depth);
            helper(root.right, total, nums, level + 1, depth);
        }
        
        public int findDepth(TreeNode root) {
            if(root == null) return 0;
            int left = findDepth(root.left);
            int right = findDepth(root.right);
            return Math.max(left, right) + 1;
        } 
    

    Intuition behind the solution:

    • Since the paths do not necessarily start or end at the root or a leaf, check the sum of a given path starting from a given node, upwards to the root.

    • For checking the sum, have an array that represents a given path. The array would be of the size of the tree ( findDepth() essentially computes the height of the tree to hold all nodes from the root to the leaf for the longest path).

    • Traverse on both sides of the tree and find the corresponding sum along the different paths.


Log in to reply
 

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