나무의 수

0보다 크거나 같은 정수 n을 입력받아서, 정확히 n개의 노드로 만들수 있는 바이너리트리의 형태의 수를 반환하는 함수를 작성합니다.

바이너리트리 토폴로지는 노드 값에 관계없이 바이너리트리 형태 구성에 관련된 정의입니다. 예를 들어 n = 2일 때, 두 개의 바이너리트리가 존재합니다: 루트노드 아래 왼쪽, 루트노드 아래 오른쪽 노드가 있는 트리입니다.

참고: n = 0이면 만들 수 있는 바이너리트리가 하나 있습니다: 루트 노드가 None / null인 바이너리트리 입니다.

예제 1

입력

n = 3

출력

5

// 세개의 노드로 만들수 있는 바이너리트리