Java O(nLogn)


  • 0
    M
    class Solution {
        public int pathSum(TreeNode root, int sum) {
            if (root == null )
                return 0;
            
            int pathsFromRoot = findPathFromNode(root, sum, 0);
            int pathsOnLeft = pathSum(root.left, sum);
            int pathsOnRight = pathSum(root.right, sum);
            
            return pathsFromRoot + pathsOnLeft + pathsOnRight;
        }
        
        private int findPathFromNode(TreeNode node, int sum, int currentSum) {
            if (node == null) {
                return 0;
            }
            
            int totalPaths = 0;
            currentSum += node.val;
            if(currentSum == sum) {
                totalPaths++;
            }
            
            totalPaths += findPathFromNode(node.left, sum, currentSum);
            totalPaths += findPathFromNode(node.right, sum, currentSum);
            return totalPaths;
        }
        
    }
    

Log in to reply
 

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