427.Path Sum

Posted on | In

Solution 1: accepted 30ms

Recursive DFS. Check all possible paths from each node.
Time: O(n^2)
Space: O(n) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        return rootSum(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
    
    // Check all paths starts from this node
    private int rootSum (TreeNode root, int sum) {
        int result = 0;
        if (root == null) return result;
        if (sum == root.val) result++;
        result += rootSum(root.left, sum - root.val);
        result += rootSum(root.right, sum - root.val);
        return result;   
    }
}