96. Unique Binary Search Trees
Tags:
Medium
Skills:
Tree
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Cho một số nguyên dương n, hãy tính số lượng cấu trúc BST khác nhau có thể tạo ra từ các số nguyên từ 1 đến n, mối số sử dụng đúng 1 lần
Hiểu về BST
- Mỗi node của cây có giá trị duy nhất
- Mọi giá trị trong cây con bên trái nhỏ hơn giá trị của node gốc
- Mọi giá trị trong cây con bên phải lơn hơn giá trị node gốc
- Cây con trái và phải cũng phải là BST
Approach
Nhận xét
- Với mỗi số i → n, nếu chọn i làm gốc thì
- Các số nhỏ hơn i nằm ở cây con bên trái (gồm i - 1 số)
- Các số lớn hơn i nằm ở cây con bên phải gồm (n - i số)
- Số lượng BST tọa được với n node là tổng các trường hợp chọn từng node làm gốc”
- dp = 1 (empty tree)
DP
- Dùng mảng dp để lưu số lượng BST ứng với từng số lượng node
- Duyệt từ 2 → n, với mỗi số lượng node, thử lần lượt từng node làm gốc, cộng dồn kết quả
Time and space complexity
- TC: O(n^2)
- SC: O(n)
Solution
typescripttypescript
1function numTrees(n: number): number {
2 const dp: number[] = new Array(n + 1).fill(0);
3 dp[0] = 1;
4 dp[1] = 1;
5 for(let nodes = 2; nodes <= n; nodes++) {
6 for(let root = 1; root <= nodes; root++) {
7 const left = root - 1;
8 const right = nodes - root;
9 dp[nodes] += dp[left] * dp[right];
10 }
11 }
12
13 return dp[n]
14};