[LeetCode/리트코드] #96. Unique Binary Search Trees[파이썬(python...

[LeetCode/리트코드] #96. Unique Binary Search Trees[파이썬(python...

https://leetcode.com/problems/unique-binary-search-trees/

BST(Binary Search Tree)는 root노드의 왼쪽으로는 더 작은 값, 오른쪽으로는 더 큰 값을 가지는 트리다.

그래서 탐색 순회하기 효율적인 자료구조를 가진다.

노드의 개수를 입력으로 받았을 때

만들 수 있는 BST의 개수를 출력으로 하면 된다.

점화식을 이용하여 풀면 시간복잡도가 굉장히 좋게 결과가 나온다.

파이썬 코드

class Solution(object): def numTrees(self, n): """ :type n: int :rtype: int """ dp = [0]*20 dp[0]=1 dp[1]=1 for i in range(2,n+1): for j in range(1,i+1): dp[i]=dp[i]+dp[j-1]*dp[i-j] return dp[n]

C++ 코드

class Solution { public: int numTrees(int n) { int dp[20]={0,}; dp[0]=1; dp[1]=1; for(int i=2;i

from http://hidemasa.tistory.com/163 by ccl(A) rewrite - 2021-11-08 18:26:34