LeetCode: Path Sum III

https://leetcode.com/problems/path-sum-iii/, which for reference, here it is:

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

 I decided to go with an O(n^2) solution given n=1000. Idea is to build an inner method that checks all the solutions given a certain node (that's the private method below), which runs in O(n). For each node in the tree, call the inner method passing the current node as the "root", making it O(n^2).
  Still fast compared to the other submissions - code's down below, thanks! Marcelo.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
    public class Solution
    {
        public int PathSum(TreeNode root, int sum)
        {
            if (root == null) return 0;
            int partialResult = 0;
            AllPathsGivenRoot(root, 0, sum, ref partialResult);
            return partialResult + PathSum(root.left, sum) + PathSum(root.right, sum);
        }

        private void AllPathsGivenRoot(TreeNode root,
                                      int currentSum,
                                      int targetSum,
                                      ref int result)
        {
            if (root == null) return;
            if (currentSum + root.val == targetSum) result++;
            AllPathsGivenRoot(root.left, currentSum + root.val, targetSum, ref result);
            AllPathsGivenRoot(root.right, currentSum + root.val, targetSum, ref result);
        }
    }