A clean backtracking solution with ~10 lines


  • 0
    A
    IList<IList<int>> resultList = new List<IList<int>>();
    
    public IList<IList<int>> PathSum(TreeNode root, int sum) 
    {
        return root == null ? PathSumUtil(root, sum, new List<int>());
    }
    
    public IList<IList<int>> PathSumUtil(TreeNode root, int sum, IList<int> prefix) 
    {
        prefix.Add(root.val);
        if(root.val == sum && root.left == null && root.right == null) 
            resultList.Add(prefix.ToList());
        else
        {
            if(root.left != null) PathSumUtil(root.left, sum - root.val, prefix);
            if(root.right != null) PathSumUtil(root.right, sum - root.val, prefix);
        }
        prefix.RemoveAt(prefix.Count - 1);
    
        return resultList;
    }

Log in to reply
 

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