Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

Return:

[
   [5,4,11,2],
   [5,8,4,5]
]

Solution

DFS Approach with Backtracking

/**
 * 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 IList<IList<int>> PathSum(TreeNode root, int sum) {
        var result = new List<IList<int>>();
        PathSumHelper(root,result,new List<int>(),sum);
        return result;
    }
    public void PathSumHelper(TreeNode root, IList<IList<int>> result, List<int> list, int sum)
    {
        if(root == null)
            return;
        
        list.Add(root.val);
        
        if(root.left == null && root.right == null && sum == root.val)
        {
            result.Add(new List<int>(list));
        }
        else
        {
            PathSumHelper(root.left,result,list,sum-root.val);
            PathSumHelper(root.right,result,list,sum-root.val);
        }
        list.RemoveAt(list.Count-1);
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s