[Leetcode] 894. All Possible Binary Trees (Python)

https://leetcode.com/problems/all-possible-full-binary-trees/

모든 가능한 이진 트리의 경우의 수를 구하는 문제이다. 

이진 트리의 노드 수가 N이라고 주어 질때 N=1, N=3, N=5 의 경우를 그림으로 표현하면 아래와 같다. 

https://anj910.medium.com/leetcode-894-all-possible-full-binary-trees-afa435ae698

그림에서 파악할 수 있듯이, N=5 의 경우 N=3이 root.left 와 root.right 에서 반복이 되고 있다. 즉, N=5에서는 N=3, N=1 에서 구한 값을 재활용하여 사용할 수 있다. 

N=7 또한 N=1, N=3, N=5의 값을 다시 활용하여 모든 경우의 수를 구할 수 있다. 또한 이진 트리는 root가 반드시 0, 그리고 자식 노드들이 항상 둘다 0 이거나 null 이므로, 노드의 개수는 항상 홀수라는 특성이 있다. 

 

https://anj910.medium.com/leetcode-894-all-possible-full-binary-trees-afa435ae698

전체 풀이는 아래와 같이 재귀 함수를 사용하여 binary tree를 만들어주고, 모든 경우의 수를 구하고 있다. 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        def make_tree(n):
            answer = []
            if n == 1: # 마지막 자식 노드
                answer.append(TreeNode(val=0))
            n -= 1 # node 하나를 미리 빼둔다. 이게 root 가 된다. 
            
            # i 가 홀수인 경우 값을 재활용 해야 함  
            for i in range(1, n+1, 2):
                left = make_tree(i) # left sub tree 노드의 개수가 i 개 이면 
                right = make_tree(n-i) # right sub tree 노드의 개수는 n-i 개가 된다. 
                
                for l in left: 
                    for r in right: 
                        # root 는 항상 val=0  
                        root = TreeNode(val=0)
                        root.left = l # root 에서부터 left, right 를 연결한다. 
                        root.right = r 
                        answer.append(root)                
            return answer 

        return make_tree(n)