Poison

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
26
27
28
29
30
31
32
33
34
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> resultList = new ArrayList<>();
        if (root == null) {
            return resultList;
        }

        List<Integer> path = new ArrayList<>();
        path.add(root.val);
        dfs(resultList, path, root, root.val, targetSum);
        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, List<Integer> path, TreeNode root, int currentSum, int targetSum) {
        if (root.left == null && root.right == null) {
            if (currentSum == targetSum) {
                resultList.add(new ArrayList<>(path));
            }
            return;
        }

        if (root.left != null) {
            path.add(root.left.val);
            dfs(resultList, path, root.left, currentSum + root.left.val, targetSum);
            path.remove(path.size() - 1);
        }

        if (root.right != null) {
            path.add(root.right.val);
            dfs(resultList, path, root.right, currentSum + root.right.val, targetSum);
            path.remove(path.size() - 1);
        }
    }
}
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
26
27
28
29
30
31
32
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if (root == null) {
            return Collections.emptyList();
        }

        List<List<Integer>> pathList = new ArrayList<>();
        Deque<Integer> path = new LinkedList<>();
        dfs(pathList, path, root, 0, target);
        return pathList;
    }

    private void dfs(List<List<Integer>> pathList, Deque<Integer> path, TreeNode node, int sum, int target) {
        sum += node.val;
        path.offer(node.val);

        if (node.left == null && node.right == null) {
            if (sum == target) {
                pathList.add(new ArrayList<>(path));
            }
        } else {
            if (node.left != null) {
                dfs(pathList, path, node.left, sum, target);
            }
            if (node.right != null) {
                dfs(pathList, path, node.right, sum, target);
            }
        }

        path.removeLast();
    }
}
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;
    }
}
Reference

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