99클럽 코테 스터디 12일차 TIL [LeetCode] All Possible Full Binary Trees (Java)

문제

[LeetCode] All Possible Full Binary Trees

풀이

동적 계획법(DP)을 활용해 가능한 완전 이진 트리를 모두 생성하는 문제

• 메모이제이션(map)을 사용하여 이미 계산된 결과를 저장한다.
• 입력 n이 짝수인 경우, 완전 이진 트리를 만들 수 없으므로 빈 리스트를 반환한다.
• n이 홀수인 경우, 모든 가능한 트리의 루트를 생성하기 위해 왼쪽과 오른쪽 서브트리의 크기를 달리하면서 재귀적으로 트리를 만든다.
• 모든 가능한 결과를 result 리스트에 추가한다.

정답 코드

class Solution {
    private Map<Integer, List<TreeNode>> memo = new HashMap<>();
    
    public List<TreeNode> allPossibleFBT(int N) {
        if (N % 2 == 0) {
            return new ArrayList<>();
        }
        if (memo.containsKey(N)) {
            return memo.get(N);
        }
        
        List<TreeNode> result = new ArrayList<>();
        if (N == 1) {
            result.add(new TreeNode(0));
        } else {
            for (int leftTreeSize = 0; leftTreeSize < N; leftTreeSize++) {
                int rightTreeSize = N - 1 - leftTreeSize;
                for (TreeNode left : allPossibleFBT(leftTreeSize)) {
                    for (TreeNode right : allPossibleFBT(rightTreeSize)) {
                        TreeNode root = new TreeNode(0);
                        root.left = left;
                        root.right = right;
                        result.add(root);
                    }
                }
            }
        }
        
        memo.put(N, result);
        return result;
    }
}