[Leetcode]894. All Possible Full Binary Trees

1. 문제 : 

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.

 

Example 1:


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]]
 

Constraints:

1 <= n <= 20

 

2. 풀이 : 

from typing import List

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def allPossibleFBT(self, n: int) -> List[TreeNode]:
        if n % 2 == 0:
            return []
        if n == 1:
            return [TreeNode(0)]
        
        result = []
        for left_tree_nodes in range(1, n, 2):
            right_tree_nodes = n - 1 - left_tree_nodes
            left_subtrees = self.allPossibleFBT(left_tree_nodes)
            right_subtrees = self.allPossibleFBT(right_tree_nodes)
            for left in left_subtrees:
                for right in right_subtrees:
                    root = TreeNode(0)
                    root.left = left
                    root.right = right
                    result.append(root)
        return result

 

이건 내가 풀지 못했다. recursion을 이용한 풀이인데, 나는 그냥 답은 똑같이 나오나, null을 제대로 처리하지 못해서, 틀렸다. 이 풀이에서 핵심은 기존에 나온 트리를 왼쪽에 붙이냐 오른쪽에 붙이냐이다. 즉, 내가 접근했던 방식과는 다르다. 나는 기존에 나왔던 트리에 노드를 하나씩 추가하는 방향이었다면, 이 방식은 왼쪽 or 오른쪽에 전에 나왔던 tree를 붙이는 방식이다. 그렇게 하기 위해서 우선 base case를 설정한다. 두 번째로 , left_node 개수를 설정한다. 이때, left_node의 개수는 홀수가 될 수밖에 없다. 왜냐하면, full_binary_tree를 만족해야 하기 때문이다. left_node의 개수가 정해지면, right_node의 개수도 정해진다. right_node = n - 1 - left_node의 개수로 구한다. 이때, 1을 빼는 이유는 root를 빼기 위함이다. 

그다음, loop를 돌며, root를 설정하고 root.left 와 root.right에 트리를 추가해 준다. 참으로 신기하다. 

 

3. 풀이 : 

from typing import List, Dict

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def __init__(self):
        self.memo: Dict[int, List[TreeNode]] = {}
    
    def allPossibleFBT(self, n: int) -> List[TreeNode]:
        if n % 2 == 0:
            return []
        if n == 1:
            return [TreeNode(0)]
        if n in self.memo:
            return self.memo[n]
        
        result = []
        for left_tree_nodes in range(1, n, 2):
            right_tree_nodes = n - 1 - left_tree_nodes
            left_subtrees = self.allPossibleFBT(left_tree_nodes)
            right_subtrees = self.allPossibleFBT(right_tree_nodes)
            for left in left_subtrees:
                for right in right_subtrees:
                    root = TreeNode(0)
                    root.left = left
                    root.right = right
                    result.append(root)
        
        self.memo[n] = result
        return result

# Helper function to print the tree in list form
def serialize(root):
    """Encodes a tree to a single string."""
    if not root:
        return "null"
    result = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append("null")
    # Remove trailing "null"s
    while result and result[-1] == "null":
        result.pop()
    return result

# Example usage
sol = Solution()
trees = sol.allPossibleFBT(7)
for tree in trees:
    print(serialize(tree))

이 풀이는 첫 번째 풀이의 단점을 보완한 방법이다. 95프로는 코드가 똑같다. 다른 점은 생성자 method를 통해 dictionary를 생성해 주고, memoization을 활용한다는 것이다. recursion을 실행할 때, dictionary에 값이 들어있으면, recursion을 종료한다. 정말 외우고 싶은 풀이다. 이렇게 하면, n == 1 or n % 2 ==0과 같은 base case까지 항상 돌아갈 필요가 없다. 

예를 들어, n = 5 일 때, n = 1을 호출할 것이다. 그다음 n = 3을 호출할 것인데, n=3일 때는 n=1로 돌아갈 필요가 없다. n=1일 때 이미 memoization 되어있기 때문이다.