UniqueBinarySearchTrees

Published at 2021-10-29

class Solution:
    def numTrees(self, n: int) -> int:
        cnts = [1, 1]  # 경우의 수 저장(0은 인덱스 맞추기 위해, 1은 노드한개일때 경우 1가지)

        for i in range(2, n + 1):
            temp = 0  # i개일때의 결과 임시로
            for left in range(0, i):  # 왼쪽노드 기준(right는 노드개수에서 left빼면됨)
                temp += cnts[left] * cnts[i - left - 1]
            cnts.append(temp)
        return cnts[n]

# 노드개수: 5개 라면
# 루트 1개 빼고 나머지 4개로 조합할 수 있음
# 왼쪽자식에 4개, 오른쪽에 0개 / 왼쪽3오른1 / 왼쪽2오른2/ 왼1오3/ 왼0오4
# 이렇게 총 5가지 조합 가능

# 그럼 첫번째 경우인 왼쪽 4 오른쪽 0 개일때를 보면
# 왼쪽에 4개중 한개는 그 서브노드의 루트로 빼고 나머지 3개로 조합할 수 있음
# 그 3개는 또 서브의 서브노드에 루트로 하나를 빼고 2개로 조합할 수 있음
# 이 과정을 거치다보면 피보나치 수열 비슷한 과정이 만들어짐

# node = 5일때 왼3오1 의 경우에서 왼쪽에는 3개를 이용해 조합할 수 있을거임
# 그럼 이 조합 마다 오른쪽에 1개를 넣는 경우를 곱해줘야함

# 그래서 식은 node=5일때
# (node[4]*node[0]) + (node[3]*node[1]) + (node[2]*node[2]) + (node[1]*node[3]) + (node[0]*node[4])