113. Path Sum II

, ,

DFS

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
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> resultList = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(resultList, path, root, 0, targetSum);
        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, List<Integer> path, TreeNode node, int sum, int targetSum) {
        if (node == null) {
            return;
        }

        path.add(node.val);
        sum += node.val;
        if (node.left == null && node.right == null && sum == targetSum) {
            resultList.add(new ArrayList<>(path));
        }

        dfs(resultList, path, node.left, sum, targetSum);
        dfs(resultList, path, node.right, sum, targetSum);

        path.remove(path.size() - 1);
    }
}

BFS

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
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if (root == null) {
            return Collections.emptyList();
        }

        List<List<Integer>> pathList = new ArrayList<>();
        Map<TreeNode, TreeNode> childToParentMap = new IdentityHashMap<>();

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        Queue<Integer> sumQueue = new LinkedList<>();
        sumQueue.offer(root.val);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            int sum = sumQueue.poll();

            if (node.left == null && node.right == null && sum == target) {
                pathList.add(getPath(node, childToParentMap));
            }

            if (node.left != null) {
                childToParentMap.put(node.left, node);
                queue.offer(node.left);
                sumQueue.offer(sum + node.left.val);
            }
            if (node.right != null) {
                childToParentMap.put(node.right, node);
                queue.offer(node.right);
                sumQueue.offer(sum + node.right.val);
            }
        }

        return pathList;
    }

    private List<Integer> getPath(TreeNode node, Map<TreeNode, TreeNode> childToParentMap) {
        LinkedList<Integer> path = new LinkedList<>();
        while (node != null) {
            path.addFirst(node.val);
            node = childToParentMap.get(node);
        }
        return path;
    }
}

References

113. Path Sum II
剑指 Offer 34. 二叉树中和为某一值的路径