113. Path Sum II

PathSum.cs

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
  public IList<IList<int>> PathSum(TreeNode root, int targetSum) {
    var currentSum = 0;
    var currentNodes = new List<int>();
    var ans = new List<IList<int>>();
    
    void Traverse(in TreeNode node){
      if(node is null)
        return;
      
      currentSum += node.val;
      currentNodes.Add(node.val);
      
      Traverse(node.left);
      Traverse(node.right);
      
      if(node.left is null && node.right is null && currentSum == targetSum)
        ans.Add(new List<int>(currentNodes));
        
      if(currentNodes.Count > 0)
        currentNodes.RemoveAt(currentNodes.Count - 1);
      currentSum -= node.val;
    }
    
    Traverse(root);
    
    return ans;    
  }
}