我正在給出一個帶有 n 個節點的二叉搜索樹，其唯一值是 1 到 n，并且需要計算我可以從中生成多少結構不同的二叉搜索樹。我使用帶有記憶功能的 DFS 來解決這個問題。基本上就像如果我們有n個節點，根節點可以從1到n，然后我遞回計算這棵樹可以有多少子樹。此外，我記住了樹可以具有的節點值范圍以及可以使用該節點值范圍制作多少種不同的樹，因此我不重新計算。我認為時間和空間都是 O(n^2)，因為我的樹節點 val 可以有 n^2 個不同的范圍。任何人都可以對此發表評論嗎？
class Solution {
public int numTrees(int n) {
// structrually unique BST with value from 1 to n
// same structure but different number? no, one way to arrange node
// from 1 to n start
// left has num candid - 1 to 1
// right has num candid 1 to n
Map<Integer, Integer> memo = new HashMap<>();
return numWays(1, n, memo);
}
private int numWays(int low, int high, Map<Integer, Integer> memo) {
if(memo.containsKey(low * 100 high)) {
return memo.get(low * 100 high);
}
if(low >= high) return 1;
int ans = 0;
for(int i = low; i <= high; i ) {
ans = ans numWays(low, i - 1, memo) * numWays(i 1, high, memo);
}
memo.put(low * 100 high, ans);
return ans;
}
}
uj5u.com熱心網友回復：
時間復雜度目前為 O(n^3)。確實只有 O(n^2) 范圍，并且最多 O(n^2) 對（低，高）作為 numWays 函式的輸入出現。然而，numWays 函式在記憶后需要 O(high-low 1) 步，這是另一個 O(n) 因素。
為了加快速度，您可能會注意到 [1,2,3,4] 的 BST 數量與 [2,3,4,5] 或 [3,4,5, 6]; 只有陣列的長度很重要（通過微小的變化為您提供 O(n^2) 演算法）。另一個可能的加速來自注意到對于每個帶n節點的有根二叉樹，只有一種方法可以用 [1,2,...,n] 標記節點以獲得 BST，所以你正在尋找一種方法/遞回計算有根二叉樹。
uj5u.com熱心網友回復：
我們也可以使用一個公式：
const f = n => n < 2 ? 1 : (4*n - 2) / (n 1) * f(n - 1);
for (let i=0; i<20; i )
console.log(f(i));轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/340407.html