Java 구현 LeetCode 113 경로 총 II

113. 경로 총 II

두 갈래 나무와 목표와 뿌리 노드에서 잎 노드까지의 모든 경로를 찾는 것은 목표와 같은 경로입니다.
설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다.
예: 다음과 같은 두 갈래 트리와 목표와sum=22,

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

반환:
[ [5,4,11,2], [5,8,4,5] ]

class Solution {
   public List> pathSum(TreeNode root, int sum) {
        if(root == null) return new ArrayList<>();
        List> ans = new ArrayList<>();
        if(root.val == sum && root.left == null && root.right == null){
            List arr = new ArrayList<>();
            arr.add(root.val);
            ans.add(arr);
            return ans;
        }
        List> left = pathSum(root.left,sum - root.val);
        List> right = pathSum(root.right,sum - root.val);
        for(List list : left){
            // 
           list.add(0,root.val);
           ans.add(list);
        }
        for(List list : right){
           list.add(0,root.val);
           ans.add(list);
        }
        return ans;
    }
}