[99클럽] 코테 스터디 17일차 TIL - DP 재귀(894. All Possible Full Binary Trees)

문제

문제 설명

int n이 주어질 때, n개의 노드로 가능한 모든 완전 이진 트리를 만들어라.
노드의 값은 모두 0이다.

제한 사항

• 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
• 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

예시

Input: n = 7
Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
Example 2:

Input: n = 3
Output: [[0,0,0]]

풀이 방법

풀이 핵심

• 완전 이진 트리를 만들기 위해서는 좌, 우 자식 노드가 모두 있거나 아예 없어야 한다.
• n개의 노드로 완전 이진 트리를 만들어야 하기 때문에 재귀를 이용하여 Top-Down 방식(Memoization 방식)으로 푼다.

풀이 로직

1. 왼쪽 자식 트리, 오른쪽 자식 트리를 각각 재귀를 이용하여 Top-Down 방식(Memoization 방식)으로 구한다.
2. 1에서 구한 자식 노드들을 조합하여 전체 트리를 구한다.
3. 1과 2를 반복하여 전체 트리들을 구한다.

코드

/**
 * 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<TreeNode> allPossibleFBT(int n) {

        // 노드가 1개인 경우
        // 🌟 메모이제이션 🌟
        if (n == 1) {
            List<TreeNode> base = new ArrayList<>();
            base.add(new TreeNode()); // 좌, 우 자식 노드가 null인 TreeNode 삽입
            return base;
        }

        List<TreeNode> result = new ArrayList<>();

        /**
        root 노드는 제외하고 시작하기 때문에 i = 1부터 시작
        자신 노드 1개, 자식 노드 2개 총 3개의 노드가 필요하기 때문에 홀수 개수만 가질 수 있다.(i+=2) 짝수 개수는 완전 이진 트리가 아니기 때문에 불가능
        전체 노드 개수(n)개 중 i개는 왼쪽 노드에 배정했기 때문에 오른쪽 노드는 전체 노드(n) - 루트 노드(1) - 왼쪽 노드(i) 개수만큼 배정한다.
        */
        // 🌟 점화식 🌟
        for (int i = 1; i < n; i += 2) {
            List<TreeNode> left = allPossibleFBT(i); // 왼쪽 자식 노드
            // 전체 노드 개수 - 루트 노드 - 왼쪽 노드 개수(n-1-i)
            List<TreeNode> right = allPossibleFBT(n - 1 - i); // 오른쪽 자식 노드

            for (TreeNode L : left) {
                for (TreeNode R : right) {
                    /**
                    root 노드(0)
                    왼쪽 자식 노드(L)
                    오른쪽 자식 노드(R)
                     */
                    TreeNode root = new TreeNode(0, L, R);
                    result.add(root);
                }
            }
        }
        return result;
    }
}

• 점화식
  • 첫 번째 for문
    • root의 왼쪽 자식 트리와 오른쪽 자식 트리에 노드의 개수를 배정한다.
    • 이때 고정값인 root를 빼기 위해 1부터 시작하고 완전 이진 트리로 만들기 위해서는 홀수 개의 노드가 필요하기 때문에 i+=2로 구성한다.
  • 두 번째 이중 for문
    • 첫 번째 for문에서 구한 left, right 자식 트리들을 조합하여 전체 트리를 구성한 후 result 리스트에 저장한다.
  • 작업을 반복하며 모든 트리를 result 리스트에 저장한 후 result를 탈출한다.

오늘 회고

오늘 문제는 처음부터 정답 코드와 유튜브 강의를 보며 이해했다.
막상 이해하면 쉬운데 나 혼자 코드를 짜는 건 왜이렇게 어려울까 ..
하다 보면 혼자서도 푸는 날이 올 거라 믿는다!!