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] ]
As described by the problem, this question is quite similar to the Path Sum I. The mainly difference is it returns all nodes in the path.
Recursive Solution:
The recursive solution is similar to Path Sum I, but saved the traversed node.
Code (Java):
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> nodes = new ArrayList<Integer>();
preOrderTraversal(root, 0, sum, result, nodes);
return result;
}
private void preOrderTraversal(TreeNode root, int pathSum, int sum, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> nodes) {
if (root == null) return;
nodes.add(root.val);
pathSum += root.val;
// root is leaf
if (root.left == null && root.right == null && pathSum == sum) {
result.add(nodes);
}
preOrderTraversal(root.left, pathSum, sum, result, new ArrayList<Integer>(nodes));
preOrderTraversal(root.right, pathSum, sum, result, new ArrayList<Integer>(nodes));
}
}
Discussion:
Note in the line 30 and 31, you should create a new object. That is because Java object is passed by "reference" (although this is not a correct statement; everything in Java is passed by value). In this case, each node maintains a separated partial list.
Iterative Solution:
The iterative solution utilized three stacks. One stores the nodes, the second stack stores the path sum, while the third one stores the partial array list.
Code (Java):
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (root == null) return result;
Stack<TreeNode> nodeStack = new Stack<TreeNode>();
Stack<Integer> sumStack = new Stack<Integer>();
Stack<ArrayList<Integer>> listStack = new Stack<ArrayList<Integer>>();
nodeStack.push(root);
sumStack.push(root.val);
ArrayList<Integer> tempList = new ArrayList<Integer>();
tempList.add(root.val);
listStack.push(tempList);
while (!nodeStack.empty()) {
TreeNode currNode = nodeStack.pop();
int pathSum = sumStack.pop();
ArrayList<Integer> list = listStack.pop();
// leaf
if (currNode.left == null && currNode.right == null && pathSum == sum) {
result.add(list);
}
if (currNode.right != null) {
nodeStack.push(currNode.right);
sumStack.push(currNode.right.val + pathSum);
ArrayList<Integer> temp = new ArrayList<Integer>(list);
temp.add(currNode.right.<Integer> temp = new ArrayList<Integer>(list);
temp.add(cal);
listStack.push(temp);
}
if (currNode.left != null) {
nodeStack.push(currNode.left);
sumStack.push(currNode.left.val + pathSum);
ArrayList<Integer> temp = new ArrayList<Integer>(list);
temp.add(currNode.left.val);
listStack.push(temp);
}
}
return result;
}
}
Update on 10/7/14:
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>>result = new ArrayList<List<Integer>>();
if (root == null) {
return result;
}
List<Integer> curList = new ArrayList<Integer>();
pathSumHelper(root, sum, 0, curList, result);
return result;
}
private void pathSumHelper(TreeNode root, int sum, int curSum, List<Integer> curList, List<List<Integer>> result) {
if (root == null) {
return;
}
curSum += root.val;
curList.add(root.val);
if (root.left == null && root.right == null && curSum == sum) {
result.add(new ArrayList(curList));
curList.remove(curList.size() - 1);
return;
}
pathSumHelper(root.left, sum, curSum, curList, result);
pathSumHelper(root.right, sum, curSum, curList, result);
curList.remove(curList.size() - 1);
}
}
A clear solution:
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (root == null) {
return result;
}
List<Integer> curList = new ArrayList<Integer>();
pathSumHelper(root, sum, 0, curList, result);
return result;
}
private void pathSumHelper(TreeNode root, int sum, int curSum, List<Integer> curList, List<List<Integer>> result) {
if (root == null) {
return;
}I
curSum += root.val;
curList.add(root.val);
if (root.left == null && root.right == null && curSum == sum) {
result.add(new ArrayList<Integer>(curList));
//curList.remove(curList.size() - 1);
}
if (root.left != null) {
pathSumHelper(root.left, sum, curSum, curList, result);
curList.remove(curList.size() - 1);
}
if (root.right != null) {
pathSumHelper(root.right, sum, curSum, curList, result);
curList.remove(curList.size() - 1);
}
}
}
Update on 11/7/2014:
A better iterative solution:
public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (root == null) {
return result;
}
Stack<TreeNode> nodeStack = new Stack<TreeNode>();
Stack&l;tInteger> levelStack = new Stack<Integer>();
int[] path = new int[1000];
nodeStack.push(root);
levelStack.push(0);
while (!nodeStack.isEmpty()) {
TreeNode currNode = nodeStack.pop();
int level = levelStack.pop();
path[level] = currNode.val;
if (currNode.left == null && currNode.right == null) {
int curSum = 0;
List<Integer> temp = new ArrayList<Integer>();
for (int i = 0; i < level + 1; i++) {
curSum += path[i];
temp.add(path[i]);
}
if (curSum == sum) {
result.add(temp);
}
}
if (currNode.right != null) {
nodeStack.push(currNode.right);
levelStack.push(level + 1);
}
if (currNode.left != null) {
nodeStack.push(currNode.left);
levelStack.push(level + 1);
}
}
return result;
}
}
Update on 4/14/15:
An iterative solution without using a path array. It is naturally an corresponding iterative solution of the recursive one.
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (root == null) {
return result;
}
Stack<TreeNode> nodeStack = new Stack<TreeNode>();
Stack<Integer> levelStack = new Stack<Integer>();
List<Integer> curList = new ArrayList<Integer>();
nodeStack.push(root);
levelStack.push(1);
int curSum = 0;
while (!nodeStack.isEmpty()) {
TreeNode curNode = nodeStack.pop();
int curLevel = levelStack.pop();
curSum += curNode.val;
// remove list elements
while (curList.size() >= curLevel) {
curSum -= curList.get(curList.size() - 1);
curList.remove(curList.size() - 1);
}
curList.add(curNode.val);
// if is a leaf node
if (curNode.left == null && curNode.right == null && curSum == sum) {
result.add(new ArrayList<Integer>(curList));
}
if (curNode.right != null) {
nodeStack.push(curNode.right);
levelStack.push(curLevel + 1);
}
if (curNode.left != null) {
nodeStack.push(curNode.left);
levelStack.push(curLevel + 1);
}
}
return result;
}
}
No comments:
Post a Comment