Leetcode 95. Unique Binary Search Trees II

문제

Given an integer n, return all the structurally unique BST's (binary search trees), 
which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

• 주어진 정수 n에 대해 1~n 의 값을 가지는 n개의 노드를 전부 사용해 만들수 있는 BST 의 모든 결과를 배열로 리턴하시오

예시

n이 3일때

• 1, 2, 3
  
• 5가지 BST 를 만들수 있다.

제한

• $1 <= n <= 8$

풀이

class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:

# left ~ right 범위의 노드값을 가지는 경우의 부분 트리를 생성해낸다.
        def generate(left, right):
        # left 와 right 가 같으면 그 노드를 리턴한다.
            if left == right:
                return [TreeNode(left)]
        # right 가 left 보다 작으면 해당하는 서브 트리가 없다.
            if left > right:
                return [None]

            res = []
            for val in range(left, right + 1):
                for leftTree in generate(left, val - 1):
                    for rightTree in generate(val + 1, right):
                    	# 해당 트리를 만들어 결과에 추가한다.
                        root = TreeNode(val, leftTree, rightTree)
                        res.append(root)
            return res

        return generate(1, n)