LeetCode 95(Unique Binary Search Trees II, Python)

1. 문제 링크

• Unique Binary Search Trees II - LeetCode

LeetCode - The World's Leading Online Programming Learning Platform

2. 문제 설명

• 이진 검색 트리(Binary Search Tree, BST)의 뜻
  • 각 노드의 값이 왼쪽 서브트리에 있는 모든 노드의 값보다 작고, 오른쪽 서브트리에 있는 모든 노드의 값보다 크다
• n이 주어졌을 때 1부터 n까지의 값을 가지는 BST를 모두 반환하기
• 예시) n=3이면 아래와 같은 5가지 가능.

1      1          2         3     3
 \      \        / \       /     /
  3      2      1   3     2     1
 /        \              /       \
2          3            1         2

3. 처음 풀이

• 1부터 n까지 n개를 배열하는 방법으로 가능한 것을 모두 만들어 둔다.(순열, makePermutation)
• [1, 3, 2]이면 위의 예시의 첫 번째 tree, [1, 2, 3]이면 두 번째 tree가 만들어짐.
• 그런데 [2, 1, 3]과 [2, 3, 1]의 경우 둘 다 같은 tree(예시의 세 번째)가 만들어짐. 따라서 두 tree가 같은 지 체크할 필요가 있음.(isSameTreee)
• 스스로 푼 것에 의의가 있지만 아주 느리다.

# 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]]:
        # 모든 순열과 결과 트리를 저장할 리스트 초기화
        resultPermutation = []
        resultTree = []

        # 순열을 생성하는 재귀 함수
        def makePermutation(path, n):
            if len(path) == n :
                resultPermutation.append(path[:])
                return
            for num in range(1, n + 1):
                if num not in path:
                    path.append(num)
                    makePermutation(path, n)
                    path.pop()
        
        # 1부터 n까지의 순열 생성
        makePermutation([], n)

        # 두 이진 트리가 동일한지 확인하는 함수
        def isSameTree(p, q):
            if not p and not q:
                return True
            if not p or not q:
                return False
            return p.val == q.val and isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

        # 각 순열을 이용하여 이진 검색 트리 생성
        for permutation in resultPermutation:
            root = TreeNode(permutation[0])
            permutation = permutation[1:]
            if permutation:
                for val in permutation:
                    cur = root
                    while cur:
                        if cur.val > val:
                            if not cur.left:
                                cur.left = TreeNode(val)
                                break
                            else:
                                cur = cur.left
                        else:
                            if not cur.right:
                                cur.right = TreeNode(val)
                                break
                            else:
                                cur = cur.right

            # 중복된 트리가 아닌 경우 결과 트리에 추가
            if resultTree:
                if all(isSameTree(root, tree) == False for tree in resultTree):
                    resultTree.append(root)
            else:
                resultTree.append(root)

        # 최종 결과 트리 리스트 반환
        return resultTree

4. 다른 풀이

• 재귀를 이용한 풀이

# 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
#Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.
#the return value are list of list


class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        # 노드가 없는 경우 빈 리스트 반환
        if n == 0:
            return []
        # 이진 검색 트리 생성 함수 호출
        return self.build(1, n)
    
    def build(self, low, high):
        # 결과 트리 리스트 초기화
        res = []
        # 범위가 역전되면 None을 추가하고 반환
        if low > high:
            res.append(None)
        # 현재 범위에서 가능한 모든 루트 노드에 대해 반복
        for i in range(low, high + 1):
            # 현재 루트를 기준으로 왼쪽 서브트리와 오른쪽 서브트리를 생성
            leftTree = self.build(low, i - 1)
            rightTree = self.build(i + 1, high)
            # 가능한 모든 서브트리의 조합에 대해 현재 루트 노드를 루트로 하는 트리 생성
            for left in leftTree:
                for right in rightTree:
                    root = TreeNode(i)
                    root.left = left
                    root.right = right
                    res.append(root)
        # 현재 범위에서 생성된 모든 트리의 리스트 반환
        return res

---

• 비슷한 풀이인데 yield를 쓴 풀이, 제너레이터를 이용하여 더 간결해짐.

# 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]]:
        def _gen_trees(left, right):
            if left == right:
                yield None
                return
            for root in range(left, right):
                for t_left in _gen_trees(left, root):
                    for t_right in _gen_trees(root+1, right):
                        yield TreeNode(root+1, t_left, t_right)
        return list(_gen_trees(0, n))

5. 배운 점

• all(iterable) 함수는 파이썬의 내장 함수 중 하나로, 주어진 iterable(반복 가능한 객체)이 모두 True 값을 갖는 경우에만 True를 반환하고, 그렇지 않으면 False를 반환

# 모든 요소가 참인 경우
result1 = all([True, 1, "hello"])
print(result1)  # 출력: True

# 하나라도 거짓인 경우
result2 = all([True, 0, "hello"])
print(result2)  # 출력: False

# 빈 iterable인 경우
result3 = all([])
print(result3)  # 출력: True

• yield는 파이썬에서 제너레이터(Generator)를 만들 때 사용되는 키워드. 제너레이터는 이터레이터(iterator)를 생성하는데 사용되며, 값을 한 번에 하나씩만 생성하고 반환하는 함수. yield를 사용하는 함수는 호출되었을 때 제어를 호출자에게 넘기고 값을 반환하지만, 함수의 상태는 보존됩니다. 다음 호출 때는 이전 상태에서 다시 시작하여 다음 값을 생성하고 반환

def my_generator():
    yield 1
    yield 2
    yield 3

# 제너레이터 객체 생성
gen = my_generator()

# next 함수를 사용하여 값에 접근
print(next(gen))  # 출력: 1
print(next(gen))  # 출력: 2
print(next(gen))  # 출력: 3