[LeetCode/113/Java]Path Sum II

[LeetCode/113/Java]Path Sum II

풀이

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        return pathSum(root, targetSum, 0, new LinkedList<Integer>(), new LinkedList<List<Integer>>());
    }
    
    public List<List<Integer>> pathSum(TreeNode root, int targetSum, int sum, List<Integer> target, List<List<Integer>> list) {
        if(root == null) return list;
        target.add(root.val);
        sum += root.val;
        if(root.left == null && root.right == null) {
            if(sum == targetSum) {
                List<Integer> temp = new LinkedList<Integer>();
                for (Integer val : target) {
                    temp.add(val);
                }
                list.add(temp);
            }
        }
        if(root.left != null) pathSum(root.left, targetSum, sum, target, list);
        if(root.right != null) pathSum(root.right, targetSum, sum, target, list);
        target.remove(target.size() - 1);
        return list;
    }
}

후기

112번 문제의 응용판입니다.

이번에는 root node에서 leap node까지의 덧셈이 지정된 값과 같은게 존재하면 해당 노드의 값을 모두 list에 담는 처리입니다.

모든 노드를 다 방문해야 하지만 노드의 값을 알아내야 하기 때문에 깊이 우선 탐색(DFS)를 이용해서 풀이를 하였습니다.

 

time complexity O(N)
space complexity O(N)