96. Unique Binary Search Trees
給定一個整數 n，返回恰好有 n 個具有唯一值（從 1 到 n）的節點的結構唯一的二元搜尋樹（BST）的數量。
範例： 輸入：n = 3 輸出：5
這表明，當有 3 個節點的時候，可以構造 5 種不同結構的二元搜尋樹。
Python
class Solution:
def numTrees(self, n: int) -> int:
# dp[i] will hold the number of unique BSTs that can be formed with i nodes
dp = [0] * (n + 1)
dp[0], dp[1] = 1, 1 # Base case: An empty tree and a single node tree
# Fill the dp array
for nodes in range(2, n + 1):
for root in range(1, nodes + 1):
left = root - 1 # Number of nodes in the left subtree
right = nodes - root # Number of nodes in the right subtree
dp[nodes] += dp[left] * dp[right]
return dp[n]
16.48MB, 41ms
C++
class Solution {
public:
int numTrees(int n) {
// Create a vector to store the number of unique BSTs for each count of nodes
std::vector<int> dp(n + 1, 0);
// Base cases
dp[0] = 1; // There is 1 way to construct a BST with 0 nodes (empty tree)
dp[1] = 1; // There is 1 way to construct a BST with 1 node
// Fill the dp array
for (int nodes = 2; nodes <= n; nodes++) {
for (int root = 1; root <= nodes; root++) {
int left = root - 1; // Number of nodes in the left subtree
int right = nodes - root; // Number of nodes in the right subtree
dp[nodes] += dp[left] * dp[right];
}
}
// The last element in dp array will hold the result for n nodes
return dp[n];
}
};
7.10MB, 3ms
Javascript
/**
* @param {number} n
* @return {number}
*/
var numTrees = function(n) {
// Array to store the number of unique BSTs for each number of nodes
const dp = new Array(n + 1).fill(0);
// Base cases
dp[0] = 1; // An empty tree is one BST
dp[1] = 1; // A single node tree is one BST
// Calculate the number of unique BSTs for each number of nodes from 2 to n
for (let nodes = 2; nodes <= n; nodes++) {
for (let root = 1; root <= nodes; root++) {
const left = root - 1; // Number of nodes in the left subtree
const right = nodes - root; // Number of nodes in the right subtree
dp[nodes] += dp[left] * dp[right];
}
}
// dp[n] will contain the result
return dp[n];
};
48.8MB, 43ms
