[LeetCode] 894 All Possible Full Binary Trees

💡 오늘의 학습 키워드

📌  완전 이진 트리

📌  재귀
📌  동적 프로그래밍

 

문제 설명

문제 링크 : https://leetcode.com/problems/all-possible-full-binary-trees/description/

Given an integer n, return a list of all possible full binary trees with n nodes.
Each node of each tree in the answer must have Node.val == 0.
Each element of the answer is the root node of one possible tree.
You may return the final list of trees in any order.
A full binary tree is a binary tree where each node has exactly 0 or 2 children.

제한 사항
1 <= n <= 20

 

문제 회고

💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지

완전 이진 트리에 적절한 자료구조를 사용해야 풀 수 있는 문제입니다. 
보통 트리 문제에서 경우의 수를 구하는 문제라면 재귀를 가장 먼저 떠올릴 수 있었습니다. 문제 해결 과정은 다음과 같습니다.

1. n 이 1일 경우 단일 노드로 구성된 트리 하나를 반환합니다.
2. n 이 1보다 클 경우 트리의 각 레벨을 순회합니다.
3. i는 왼쪽 서브트리에 속하는 노드의 개수를 의미합니다.
4. 완전 이진 트리는 노드 수가 홀수이어야 하므로 홀수로 순회하고 왼쪽, 오른쪽 트리를 재귀적으로 순회합니다.
5. 재귀 함수를 통해 생성된 모든 조합 가능한 트리를 answer 리스트에 저장하여 반환합니다.

 

왼쪽, 오른쪽 서브 트리를 적절하게 나누고 경우의 수를 저장하는 문제였습니다.

해당 경우의 수를 재귀를 사용하여 계산하는게 가장 일반론적인 방법으로 풀이되었지만, 보통 이렇게 재귀를 사용할 경우
동일한 부분의 문제를 여러 번 해결해야 하는 경우가 생깁니다. 즉, 트리 구성 과정에 같은 서브 트리 조합이 여러 번
계산될 수 있는 것입니다. 

 

이 문제를 해결하기 위해 @cache 데코레이터를 사용해 함수 결과를 캐시하는 방식을 사용하는 코드도 있었고,
동적 프로그래밍 즉 DP 자료구조를 사용하여 메모제이션 또는 캐싱을 통해 저장하는 방식을 사용하는 코드도 있었습니다.
DP에서 이전 단계의 결과를 활용하는 부분이 재귀의 오버헤드를 감소시키고, 공간 복잡도를 개선하여
더 빠르고 효율적인 결과가 리턴할 수 있습니다. 그럼에도 문제 자체가 트리, 그래프 탐색이나 분할 정복과 같이
재귀적으로 정의되거나 문제 크기가 작을 때에는 간결하고 직관적인 재귀 방식이 적절할 수 있습니다.

만약 메모리 제한이 있거나 제한사항이 까다로운 성능이 중요한 문제라면 재귀보다 DP 방식을 사용하는게 적절할 것입니다.

 

💡 내가 해결한 방식은?

재귀를 사용한 풀이 (174ms)

class Solution:
    # 변수에 None 값이 들어갈 수 있다면 Optional 사용
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        answer = []
        
        # n이 1일 경우
        if n == 1:
            return [TreeNode(0)]
        
        # n이 1보다 클 경우
        # 완전 이진 트리는 홀수만 탐색
        for i in range(1, n, 2):
            left_trees = self.allPossibleFBT(i)
            right_trees = self.allPossibleFBT(n-i-1)
            
            for left_tree in left_trees:
            	for right_tree in right_trees:
                    root = TreeNode(0)
                    root.left = left_tree
                    root.right = right_tree
                    answer.append(root)
                    
        return answer

dp를 이용한 풀이 (92ms)

class Solution:
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        # dp 배열 초기화
    	dp = [[] for _ in range(n+1)]
        # 하나 노드를 가진 트리 추가
        dp[1].append(TreeNode(0))
        
        # 완전 이진 트리를 위한 노드 수가 3 이상인 경우 처리
        for i in range(3, n+1, 2):
            # 왼쪽, 오른쪽 서브 트리 나누기
            # 왼쪽 노드 수는 1 부터 i-2 까지 홀수인 경우입니다.
            for lt in range(1, i-1, 2):
            	rt = i - lt - 1
                for left in dp[lt]:
                    for right in dp[rt]:
                        dp[i].append(TreeNode(0, left, right))
        return dp[n]

 

---

✍️  TIL

분명 비슷한 유형을 풀었는데 왜 또 이렇게 새로운 건지.. 가끔은 나올때마다 틀리고 정리만 무한으로 하는게 아닌지.. 한번만 맞추고 싶다
완전 이진 트리의 특성의 이해와 별개로 코드에서 저 TreeNode 별개의 클래스에서 객체화된 트리를 다루는 데
익숙해져야 빠르고 정확하게 풀 수 있을 것 같다. DP를 사용했을 때 시간 복잡도가 절반이 줄어드는 것을 기억하고
DP를 활용해 풀 수 있는 문제는 머리에 남겨두기.. DP는 진짜 활용하는게 적응이 안된다..
오른쪽 왼쪽 서브트리를 올바른 범위로 나누는 것만 잘한다면 응용되어 다른 문제가 나와도 접근 자체는 해볼 수 있을 것 같다.