Leetcode(113) Path Sum II

发表于 | 分类于

Description

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,

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

Return:

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

解法

与之前的题目类似，不过需要记录路径，同样采用递归的方法解题，注意list中元素为整型时的删除操作，这里采用index的方式删除，如果对应元素删除的话需转换成Integer类型。

具体代码如下：

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
class Solution {
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null)
            return res;
        findpath(root, sum, 0, new ArrayList<>());
        return res;
    }

    void findpath(TreeNode root, int sum, int now, List<Integer> tmp) {
        if (root == null) {
            return;
        }
        now = now + root.val;
        tmp.add(root.val);
        if (root.left == null && root.right == null) {
            if (now == sum) {
                List<Integer> path = new ArrayList<>();
                for (int node :
                        tmp) {
                    path.add(node);
                }
                res.add(path);
            }
            tmp.remove(tmp.size() - 1);
            return;
        }
        findpath(root.left, sum, now, tmp);
        findpath(root.right, sum, now, tmp);
        tmp.remove(tmp.size() - 1);
    }
}