113. Path Sum II

문제

https://leetcode.com/problems/path-sum-ii/description/

풀이

class Solution {
    List<List<Integer>> answer = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        DFS(root, targetSum, 0, new ArrayList<>());
        return answer;
    }

    public void DFS(TreeNode node, int targetSum, int sum, List<Integer> list) {
        if(node == null) {
            return;
        }
        
        list.add(node.val);
        sum += node.val;

        if(node.left == null && node.right == null) {
            if(sum == targetSum) {
              answer.add(new ArrayList<>(list)); // 복제
          }
        }

        DFS(node.left, targetSum, sum, list);
        DFS(node.right, targetSum, sum, list);
        list.remove(list.size() - 1);
    }
}

• leaf까지 왔을 때, 합이 같다면 List를 add
• 백트래킹할 때 맨 마지막 인덱스를 remove하면서 현재까지의 노드 List를 관리