99클럽 코테 스터디 18일차 TIL + Dynamic Programming/Tree/Recursion/Memoization/Binary Tree: All Possible Full Binary Trees

문제

링크텍스트

풀이

class Solution:
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        if n == 1: 
            return [TreeNode(0)]
        lFBT = []
        if n % 2 == 0: 
            return lFBT
        if n == 3:
            l = TreeNode(0)
            r = TreeNode(0)
            c = TreeNode(0,l,r)
            return [c]
        for i in range(n):
            for l in self.allPossibleFBT(n - i - 1):
                for r in self.allPossibleFBT(i):
                    root = TreeNode(0, l, r)
                    lFBT.append(root)
        return lFBT

• tree 어렵습니다. 재귀함수를 사용하였습니다.
• n이 짝수면 FBT (Full Binary Tree)를 만들 수 없습니다.
• 가장 기본의 형태 (n == 3)을 기준으로 하여, n이 그보다 큰 경우에는 아랫단의 좌우에 배치할 수 있는 모든 경우를 훑어 나갑니다.
• 문제 풀이에 너무 많은 시간을 쓰고도 답을 못 찾는데 같은 종류의 문제가 다시 나오면 풀 수 있기만을 바랍니다.
• 예전에 만들어 놓은 class tn에 오류가 있음을 확인했습니다. 수정이 필요합니다.

결과