Massive Algorithms: LeetCode

LeetCode - Path Sum II

LeetCode - Path Sum
Related: LeetCode 437 - Path Sum III
LeetCode - Path Sum II | Darren's Blog

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

For 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]
]

add a node to the list
recur its left child and right child
remove this node from the list before backtracking (previous condition would be restored)

public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {

        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

        if (root == null)

            return result;

        recursivePathSum(root, sum, new ArrayList<Integer>(), result);

        return result;

}

    private void recursivePathSum(TreeNode root, int sum, ArrayList<Integer> current,

                                  ArrayList<ArrayList<Integer>> result) {

        if (root == null)   // Empty tree

            return;

        // It is a leaf and its value is the path sum

        if (root.val == sum && root.left == null && root.right == null) {

            // Add the node into the current path, and store that path before recover the path

            current.add(root.val);

            result.add(new ArrayList<Integer>(current));

            current.remove(current.size()-1);//

            return;

}

        // Add the node into the current path, and explore its left subtree and right subtree

        // before recover the path

        current.add(root.val);

        recursivePathSum(root.left, sum-root.val, current, result);

        recursivePathSum(root.right, sum-root.val, current, result);

        current.remove(current.size()-1);

}

Recursive like the Question 66, just use a vector<int> to store the result.
Just don't forget the backtracking.
After searching the left node and right node, DO NOT forget to pop the node added in the vector.
Ideas see Question 66.
Details see code below:
Java Code From: http://rleetcode.blogspot.com/2014/02/path-sum-ii-java.html
https://leetcode.com/discuss/16980/dfs-with-one-linkedlist-accepted-java-solution
Using ArrayList as a stack

public List<List<Integer>> pathSum(TreeNode root, int sum){
 List<List<Integer>> result  = new LinkedList<List<Integer>>();
 List<Integer> currentResult  = new LinkedList<Integer>();
 pathSum(root,sum,currentResult,result);
 return result;
}

public void pathSum(TreeNode root, int sum, List<Integer> currentResult,
  List<List<Integer>> result) {

 if (root == null)
  return;
 currentResult.add(new Integer(root.val));
 if (root.left == null && root.right == null && sum == root.val) {
  result.add(new LinkedList(currentResult));
  currentResult.remove(currentResult.size() - 1);//don't forget to remove the last integer
  return;
 } else {
  pathSum(root.left, sum - root.val, currentResult, result);
  pathSum(root.right, sum - root.val, currentResult, result);
 }
 currentResult.remove(currentResult.size() - 1);
}

https://leetcode.com/discuss/76870/my-simple-java-solution
Previous one is better, this creates two many lists that are not valid answers.
private List<List<Integer>> result = new ArrayList<List<Integer>>(); public List<List<Integer>> pathSum(TreeNode root, int sum) { helper(new ArrayList<Integer>(), root, sum); return result; } private void helper(List<Integer> list, TreeNode root, int sum) { if (root == null) return; list.add(root.val); sum -= root.val; if (root.left == null && root.right == null) { if (sum == 0) result.add(list); return; } helper(new ArrayList<Integer>(list), root.left, sum); helper(new ArrayList<Integer>(list), root.right, sum); }
http://www.jiuzhang.com/solutions/path-sum-ii/
https://discuss.leetcode.com/topic/13657/simple-dfs-java-solution

    private List<List<Integer>> resultList = new ArrayList<List<Integer>>();
    
    public void pathSumInner(TreeNode root, int sum, Stack<Integer>path) {
        path.push(root.val);
        if(root.left == null && root.right == null)
            if(sum == root.val) resultList.add(new ArrayList<Integer>(path));
        if(root.left!=null) pathSumInner(root.left, sum-root.val, path);
        if(root.right!=null)pathSumInner(root.right, sum-root.val, path);
        path.pop();
    }
    
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if(root==null) return resultList;
        Stack<Integer> path = new Stack<Integer>();
        pathSumInner(root, sum, path);
        return resultList;
    }

http://www.jyuan92.com/blog/leetcode-path-sum-ii/

public List<List<Integer>> pathSum(TreeNode root, int sum) {

   List<List<Integer>> res = new ArrayList<List<Integer>>();

   helper(root, res, new ArrayList<Integer>(), sum);

   return res;

}

private void helper(TreeNode root, List<List<Integer>> res, List<Integer> temp, int sum) {

   if (null == root) {

       return;

}

   temp.add(root.val);

   if (null == root.left && null == root.right && sum == root.val) {

       res.add(new ArrayList<Integer>(temp));

}

   helper(root.left, res, temp, sum - root.val);

   helper(root.right, res, temp, sum - root.val);

   temp.remove(temp.size() - 1);

}

X. Not easy to understand

https://leetcode.com/discuss/12699/my-accepted-java-solution
public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> pathList = new ArrayList<List<Integer>>(); if(root==null){ return pathList; } if(root.left==null&&root.right==null){//if find a path, create a new list and add to the pathList. if(root.val==sum){ List<Integer> list = new ArrayList<Integer>(); list.add(root.val); pathList.add(list); } return pathList; } //find path left and right child and merge two list together. pathList = pathSum(root.left, sum-root.val); List<List<Integer>> pathList_right = pathSum(root.right, sum-root.val); for(List<Integer> l:pathList_right){ pathList.add(l); } //add current root to every list in path list. for(List<Integer> l:pathList){ l.add(0, root.val); } return pathList; }

https://github.com/rffffffff007/leetcode/blob/master/Path%20Sum%20II.java
public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
pathSum(root, sum, res, new ArrayList<Integer>());
return res;
}

private void pathSum(TreeNode root, int sum, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list){
if(root == null)
return;
list.add(root.val);
sum -= root.val;
if(root.left == null && root.right == null && sum == 0)
res.add(new ArrayList<Integer>(list));
else{
pathSum(root.left, sum, res, list);
pathSum(root.right, sum, res, list);
}
list.remove(list.size() - 1);
}
http://www.programcreek.com/2014/05/leetcode-path-sum-ii-java/
Code is cleaner if we check null as base case: as we just need check once.

public List<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    if(root == null) 
        return result;
 
    ArrayList<Integer> l = new ArrayList<Integer>();
    l.add(root.val);
    dfs(root, sum-root.val, result, l);
    return result;
}
 
public void dfs(TreeNode t, int sum, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> l){
    if(t.left==null && t.right==null && sum==0){
        ArrayList<Integer> temp = new ArrayList<Integer>();
        temp.addAll(l);
        result.add(temp);
    }
 
    //search path of left node
    if(t.left != null){
        l.add(t.left.val);
        dfs(t.left, sum-t.left.val, result, l);
        l.remove(l.size()-1);
    }
 
    //search path of right node
    if(t.right!=null){
        l.add(t.right.val);
        dfs(t.right, sum-t.right.val, result, l);
        l.remove(l.size()-1);
    }
}

http://blog.sina.com.cn/s/blog_6db692830102v0oe.html
Read full article from LeetCode - Path Sum II | Darren's Blog

LeetCode - Path Sum II

Labels

Popular Posts