不同的二叉搜索樹

南一道街丶 2022-01-07 19:02:18 阅读数:62

不同 二叉 搜索

題目如下:

在這裏插入圖片描述

第一種思路:

用for循環遍曆左右子樹遞歸的結果之和

為什麼這樣說呢,因為如果你設定中間的2為根的話,那麼當前的不同二叉搜索樹的結果就是根的左邊排列個數根的右邊排列個數,如果取1為中間值也是如此,所以就需要我們使用for循環遍曆i(i為1到n)為根的所有情况,計算他們的情况之和

代碼如下:

int numTrees(int n) {

// 計算閉區間 [1, n] 組成的 BST 個數
return count(1, n);
}
/* 計算閉區間 [lo, hi] 組成的 BST 個數 */
int count(int l, int r) {

// base case
if (l > r) return 1;
int res = 0;
for (int i = l; i <= r; i++) {

// i 的值作為根節點 root
int left = count(l, i - 1);
int right = count(i + 1, r);
// 左右子樹的組合數乘積是 BST 的總數
res += left * right;
}
return res;
}

缺點:

結果需要一步一步計算累加出來,重複子問題過多

優化前:

在這裏插入圖片描述

改良:

該問題的複雜度很高,存在著重疊子問題,所以加一個二維數組memo做備忘錄,如果備忘錄裏面有的直接返回備忘錄的數組值即可, 如果沒有的繼續進行

優化代碼:

int[][] memo;
int numTrees(int n) {

// 備忘錄的值初始化為 0
memo = new int[n + 1][n + 1];
return count(1, n);
}
int count(int l, int r) {

if (l > r) return 1;
// 查備忘錄
if (memo[l][r] != 0) {

return memo[l][r];
}
int res = 0;
for (int mid = l; mid <= r; mid++) {

int left = count(l, mid - 1);
int right = count(mid + 1, r);
res += left * right;
}
// 將結果存入備忘錄
memo[l][r] = res;
return res;
}

優化後:

在這裏插入圖片描述

第二種思路:

第二種思路采用動態規劃的思想,將父問題拆分成若幹個子問題的解,解决這類問題,首先要講子問題的解確定,在這裏我們確定num[0] = 1 ,num[1] = 1,則有遞推公式

 for (int i = 2; i <= n; ++i) {

for (int j = 1; j <= i; ++j) {

num[i] += num[j - 1] * num[i - j];
}
}

代碼如下:

class Solution {

public int numTrees(int n) {

int[] num = new int[n + 1];
num[0] = 1;
num[1] = 1;
for (int i = 2; i <= n; ++i) {

for (int j = 1; j <= i; ++j) {

num[i] += num[j - 1] * num[i - j];
}
}
return num[n];
}
}

時間效率:

在這裏插入圖片描述

版权声明:本文为[南一道街丶]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201071902183636.html