[99클럽 코테 스터디 18일차 TIL] DP

✏️  오늘의 문제 : 894. All Possible Full Binary Trees

 

 

📌 주안점

• n개의 노드로 이루어진 모든 full binary tree를 구하기 위해선 크게 세가지를 생각해볼 수 있다.
  • 최소 갯수의 노드로 이루어진 full binary tree
  • root로부터 최소 갯수의 노드 이후로 남은 노드가 있다면, 왼쪽 혹은 오른쪽으로 가지를 뻗어야 한다.
    • 한쪽으로 가지를 뻗을 때, 반대 방향으로 뻗을 노드의 갯수를 정할 수 있다.
  • 남은 노드의 갯수가 1개라면, 리프 노드를 담당한다.
• 정리하면, 노드 갯수가 3개 남은 상태에서는 node, node->left, node->right만 가능하다.
• 노드 갯수가 n개인 상황에서, 왼쪽으로 k개의 노드를 분배한다면 오른쪽으로는 n-k-1개의 노드가 분배된다(현재 참조하고 있는 노드(root)를 제외)
  • n개인 상황에서는, k개의 왼쪽으로 노드를 뻗은 완전이진트리와 n-k-1개의 오른쪽으로 노드를 뻗은 완전이진트리가 존재한다. (반복되는 동일한 구조)

 

📌 풀이

• 코드의 흐름은, n개의 노드가 주어졌다면 1,3,5,...개의 노드를 왼쪽으로 뻗는다.
• 왼쪽으로 뻗는 경우 1,3,5,...개마다 오른쪽 노드에 대해서도 마찬가지로 allPossibleFBT를 수행한다.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def allPossibleFBT(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        if n%2 == 0:
            return []
        if n==1:
            return [TreeNode(0)]
        res = []
        for i in range(1,n,2):
            for l in self.allPossibleFBT(i):
                for r in self.allPossibleFBT(n-i-1):
                    root = TreeNode(0)
                    root.left = l
                    root.right = r
                    res.append(root)

        return res