資訊專欄INFORMATION COLUMN
摘要：在這里我們使用數(shù)組中下標(biāo)為的位置來(lái)記錄個(gè)元素可以組成的平衡二叉樹的數(shù)量。在遞歸的過(guò)程中，我們找到以當(dāng)前節(jié)點(diǎn)作為根節(jié)點(diǎn)的所有平衡二叉樹，并將結(jié)果以形式返回上一級(jí)調(diào)用。
題目要求
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-n這n-1個(gè)數(shù)字可以構(gòu)成的全部搜索二叉樹以及其個(gè)數(shù)。
思路和代碼如果只是單純的計(jì)算二叉樹的數(shù)量，其實(shí)這就完全轉(zhuǎn)化成了一道規(guī)律題。我們可以從1開始尋找規(guī)律。
1： 1
1，2： 12， 21
1，2，3：123，132，213，312，321
我們可以通過(guò)dp的方式來(lái)記錄。無(wú)論以哪一個(gè)節(jié)點(diǎn)作為root節(jié)點(diǎn)，它的左子樹的元素和右子樹的元素都是固定的。也就是說(shuō)，假設(shè)root值為i，那么左子樹的元素為[1...i-1],右子樹的元素為[i+1...n]。因此當(dāng)前root節(jié)點(diǎn)可以生成的平衡二叉樹數(shù)量即為左子樹數(shù)量*右子樹數(shù)量。在這里我們使用int[]數(shù)組中下標(biāo)為n的位置來(lái)記錄n個(gè)元素可以組成的平衡二叉樹的數(shù)量。
public int numTrees(int n) {
int[] nums = new int[n+1];
for(int i = 0 ; i <= n ; i++){
if(i==0 || i==1) nums[i] = 1;
else{
for(int j = 1 ; j<=i ; j++){
nums[i] += nums[j-1]*nums[i-j];
}
}
}
return nums[n];
}
如果要我們返回具體樹的形態(tài)的話，就需要我們通過(guò)backtracking的遞歸形式來(lái)找到所有的平衡二叉樹。在遞歸的過(guò)程中，我們找到以當(dāng)前節(jié)點(diǎn)作為根節(jié)點(diǎn)的所有平衡二叉樹，并將結(jié)果以list形式返回上一級(jí)調(diào)用。
public ListgenerateTrees(int n) { if(n==0) return new ArrayList (); return generateTrees(1,n); } public List generateTrees(int start, int end){ List result = new ArrayList (); if(start>end){ result.add(null); }else if(start==end){ result.add(new TreeNode(start)); }else{ for(int i = start ; i<=end ; i++){ List left = generateTrees(start, i-1); List right = generateTrees(i+1, end); for(TreeNode tempLeft : left){ for(TreeNode tempRight : right){ TreeNode root = new TreeNode(i); root.left = tempLeft; root.right = tempRight; result.add(root); } } } } return result; }
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/67545.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ù)，就是根為到的樹相加。所以該問(wèn)題化簡(jiǎn)為以為根，其唯一左子樹和右子樹各有多少，這就是個(gè)動(dòng)態(tài)規(guī)劃的問(wèn)題了。 Unique Binary Search Trees I && II 解法請(qǐng)見(jiàn)：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...
Unique Binary Search TreesGiven n, how many structurally unique BSTs (binary search trees) that store values 1...n? For example,Given n = 3, there are a total of 5 unique BSTs. 1 3 3 ...
摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...
閱讀 2606·2021-11-18 10:02
閱讀 2638·2021-11-15 11:38
閱讀 3717·2021-11-12 10:36
閱讀 708·2021-11-12 10:34
閱讀 2907·2021-10-21 09:38
閱讀 1496·2021-09-29 09:48
閱讀 1507·2021-09-29 09:34
閱讀 1102·2021-09-22 10:02
