[LeetCode] PathSum II

Problem: Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where each path's sum equals targetSum.

A leaf is a node with no children.

Example:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]

Input: root = [1,2,3], targetSum = 5
Output: []

Input: root = [1,2], targetSum = 0
Output: []

Approach: We can use PreOrder Traversal to solve this problem easily.

Implementation in C#:

    public IList<IList<int>> PathSum(TreeNode root, int targetSum) 

    {

        List<IList<int>> result = new List<IList<int>>();

        if (root == null)

        {

            return result;

        }

        int currSum = 0;

        List<int> currNums = new List<int>();

        this.AllPathSums(root, targetSum, currSum, currNums, result);

        return result;

    }

    

    private void AllPathSums(

        TreeNode node, 

        int targetSum, 

        int currSum, 

        List<int> currNums,

        List<IList<int>> result

    )

    {

        if (node == null)

        {

            return;

        }

        currSum += node.val;

        currNums.Add(node.val);

        if (node.left == null && node.right == null)

        {

            if (currSum == targetSum)

            {

                result.Add(new List<int>(currNums));

            }

        }

        this.AllPathSums(node.left, targetSum, currSum, currNums, result);

        this.AllPathSums(node.right, targetSum, currSum, currNums, result);

        currSum -= node.val;

        currNums.RemoveAt(currNums.Count - 1);

    }

Complexity: O(n)