資訊專欄INFORMATION COLUMN
Unique Binary Search Trees
Given n, how many structurally unique BST"s (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST"s.
1 3 3 2 1
/ / /
3 2 1 1 3 2
/ /
2 1 2 3
1.解題思路
本題求1...n可以組成的二叉搜索樹的種數(shù)，我們很容易想到用動(dòng)態(tài)規(guī)劃來(lái)做，尋找狀態(tài)，dp[i]來(lái)表示1..i個(gè)節(jié)點(diǎn)可以有的種數(shù)，狀態(tài)轉(zhuǎn)移，我們可以發(fā)現(xiàn)對(duì)于每一個(gè)根節(jié)點(diǎn)，它所能出現(xiàn)的二叉樹種類就等于它的左子樹種類*它的右子樹種類，而且i來(lái)說(shuō)，可以選取1..i中的任意一個(gè)節(jié)點(diǎn)作為根。
狀態(tài)轉(zhuǎn)移方程就出來(lái)了。
dp[i]+=dp[root-1]*dp[i-root]; 1<=root<=i;
2.代碼
public class Solution {
public int numTrees(int n) {
if(n==0) return 0;
int[] dp=new int[n+1];
dp[0]=1;
for(int i=1;i<=n;i++){
for(int root=1;root<=i;root++){
dp[i]+=dp[root-1]*dp[i-root];
}
}
return dp[n];
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/69813.html
Unique Binary Search Trees Problem Given n, how many structurally unique BSTs (binary search trees) that store values 1...n? Example Given n = 3, there are a total of 5 unique BSTs. 1 3 3...
摘要：而根可以選擇從到的任意的數(shù)，唯一二叉樹的總數(shù)，就是根為到的樹相加。所以該問題化簡(jiǎn)為以為根，其唯一左子樹和右子樹各有多少，這就是個(gè)動(dòng)態(tài)規(guī)劃的問題了。 Unique Binary Search Trees I && II 解法請(qǐng)見：https://yanjia.li/zh/2019/02/... Given n, how many structurally unique BSTs (b...
摘要：題目解讀窮舉列出所有二叉樹的結(jié)構(gòu)類型。重點(diǎn)動(dòng)態(tài)規(guī)劃，關(guān)注臨近，，之間的關(guān)系應(yīng)用窮舉組合，動(dòng)態(tài)規(guī)劃窮舉組合，適用于相鄰元素有規(guī)律。處注意邊界值的情況。不能有重復(fù)，遺漏。 題目解讀： 窮舉列出所有二叉樹的結(jié)構(gòu)類型。重點(diǎn)： 動(dòng)態(tài)規(guī)劃，關(guān)注臨近root，left，right之間的關(guān)系應(yīng)用：窮舉組合，動(dòng)態(tài)規(guī)劃窮舉組合，適用于相鄰元素有規(guī)律。bug處：注意邊界值的情況。不能有重復(fù)，遺漏。 clas...
摘要：遞歸法復(fù)雜度時(shí)間空間思路根據(jù)二叉樹的性質(zhì)，我們知道當(dāng)遍歷到某個(gè)根節(jié)點(diǎn)時(shí)，最近的那個(gè)節(jié)點(diǎn)要么是在子樹里面，要么就是根節(jié)點(diǎn)本身。因?yàn)槲覀冎离x目標(biāo)數(shù)最接近的數(shù)肯定在二叉搜索的路徑上。 Closest Binary Search Tree Value I Given a non-empty binary search tree and a target value, find the va...
Problem Given a root of Binary Search Tree with unique value for each node. Remove the node with given value. If there is no such a node with given value in the binary search tree, do nothing. You sho...
閱讀 2580·2021-09-06 15:02
閱讀 3213·2021-09-02 10:18
閱讀 2835·2019-08-30 15:44
閱讀 695·2019-08-30 15:43
閱讀 1959·2019-08-30 14:08
閱讀 2767·2019-08-30 13:16
閱讀 1408·2019-08-26 13:52
閱讀 939·2019-08-26 12:21
