Monday, August 18, 2014

Leetcode: 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.
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]
]

Understand the problem:
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):
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 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):
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * 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:
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * 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<integer>(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);
    }
}
</integer>

 A clear solution:
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * 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:
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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. 
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * 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;
    }
}
Posted by at
Labels: , ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)