卖萌的弱渣

I am stupid, I am hungry.

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.

Example:

Given the below binary tree and sum = 22,

1
2
3
4
5
6
7
8
9
10
11
12

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \    / \
    7    2  5   1
return
[
   [5,4,11,2],
   [5,8,4,5]
]

Solution

  • DFS search all path (search until the leaf)

  • Java

(Path-Sum2.java) download
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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {

    List<List<Integer>> ret = new LinkedList<List<Integer>>();
    List<Integer> tmp = new LinkedList<Integer>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null)
            return ret;
        dfs(root, sum);
        return ret;
    }

    public void dfs(TreeNode root, int sum){
        tmp.add(root.val);
        if (sum == root.val && root.left==null && root.right==null) {
            ret.add(new LinkedList(tmp));
            return ;
        }

        if (root.left != null){
            dfs(root.left, sum-root.val);
            tmp.remove(tmp.size()-1);
        }
        if (root.right != null){
            dfs(root.right, sum-root.val);
            tmp.remove(tmp.size()-1);
        }

    }
}
  • Python
(Path-Sum2.py) download
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

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):

    def findPath(self,result,vector,node,bal):
        vector.append(node.val)
        if node.val == bal and node.left == None and node.right == None:
            result.append(vector[:])
            return

        if node.left != None:
            self.findPath(result,vector,node.left,bal-node.val)
            vector.pop()
        if node.right != None:
            self.findPath(result,vector,node.right,bal-node.val)
            vector.pop()
        return




    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """

        result = []
        vector = []
        if root == None:
            return result

        self.findPath(result,vector,root,sum);
        return result