95. Unique Binary Search Trees II

95. Unique Binary Search Trees II

 

https://youtu.be/m907FlQa2Yc?si=0uoBNIz-4bKCMaD8

 

# 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 generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        # n개의 노드로 생성 가능한 모든 고유한 BST를 반환하는 함수
        # Function to return all unique BSTs that can be generated with n nodes

        def generate(left, right):
            # 주어진 범위 [left, right]로 생성 가능한 모든 BST를 반환하는 재귀 함수
            # Recursive function to return all BSTs for the range [left, right]
            if left == right:
                # left와 right가 같으면 하나의 노드만 가지는 트리를 반환
                # If left equals right, return a single-node tree
                
                # 이 조건은 범위에 단 하나의 값만 남았을 때 작동합니다.
                # 루트로 사용할 값이 left 또는 right 하나뿐이므로,
                # 해당 값을 가진 단일 노드만 반환됩니다.
                # This condition handles the case where only one value remains in the range.
                # Since the root can only be the value of left or right, 
                # a single-node tree is returned.
                return [TreeNode(left)]

            if left > right:
                # left가 right보다 크면 유효하지 않은 트리이므로 None을 포함한 리스트를 반환
                # If left is greater than right, return a list containing None (invalid tree)
                return [None]

            res = []  # 현재 범위에서 가능한 모든 트리를 저장할 리스트
            # List to store all possible trees for the current range
            for val in range(left, right+1):
                # 현재 루트 노드로 val을 선택
                # Choose val as the root node
                for leftTree in generate(left, val-1):
                    # 왼쪽 서브트리는 [left, val-1] 범위로 재귀 호출하여 생성
                    # Generate left subtree using the range [left, val-1]
                    for rightTree in generate(val+1, right):
                        # 오른쪽 서브트리는 [val+1, right] 범위로 재귀 호출하여 생성
                        # Generate right subtree using the range [val+1, right]
                        root = TreeNode(val, leftTree, rightTree)
                        # 현재 노드를 루트로 왼쪽과 오른쪽 서브트리를 연결
                        # Connect the current node as root with left and right subtrees
                        res.append(root)
                        # 생성된 트리를 결과 리스트에 추가
                        # Add the generated tree to the result list
            return res  # 가능한 모든 트리를 반환
            # Return all possible trees

        return generate(1, n)  # 1부터 n까지의 숫자로 트리를 생성
        # Generate trees using numbers from 1 to n

 

if left == right: return [TreeNode(left)] 이게 어떤경우야? 그리고 왜 왼쪽만 반환해?