資訊專欄INFORMATION COLUMN
摘要：在這里我們使用數(shù)組中下標(biāo)為的位置來記錄個元素可以組成的平衡二叉樹的數(shù)量。在遞歸的過程中，我們找到以當(dāng)前節(jié)點作為根節(jié)點的所有平衡二叉樹，并將結(jié)果以形式返回上一級調(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個數(shù)字可以構(gòu)成的全部搜索二叉樹以及其個數(shù)。
思路和代碼如果只是單純的計算二叉樹的數(shù)量，其實這就完全轉(zhuǎn)化成了一道規(guī)律題。我們可以從1開始尋找規(guī)律。
1： 1
1，2： 12， 21
1，2，3：123，132，213，312，321
我們可以通過dp的方式來記錄。無論以哪一個節(jié)點作為root節(jié)點，它的左子樹的元素和右子樹的元素都是固定的。也就是說，假設(shè)root值為i，那么左子樹的元素為[1...i-1],右子樹的元素為[i+1...n]。因此當(dāng)前root節(jié)點可以生成的平衡二叉樹數(shù)量即為左子樹數(shù)量*右子樹數(shù)量。在這里我們使用int[]數(shù)組中下標(biāo)為n的位置來記錄n個元素可以組成的平衡二叉樹的數(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)的話，就需要我們通過backtracking的遞歸形式來找到所有的平衡二叉樹。在遞歸的過程中，我們找到以當(dāng)前節(jié)點作為根節(jié)點的所有平衡二叉樹，并將結(jié)果以list形式返回上一級調(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)注我的微信公眾號！將會不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/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ù)，就是根為到的樹相加。所以該問題化簡為以為根，其唯一左子樹和右子樹各有多少，這就是個動態(tài)規(guī)劃的問題了。 Unique Binary Search Trees I && II 解法請見：https://yanjia.li/zh/2019/02/... Given n, how many structurally unique BSTs (b...
摘要：題目解讀窮舉列出所有二叉樹的結(jié)構(gòu)類型。重點動態(tài)規(guī)劃，關(guān)注臨近，，之間的關(guān)系應(yīng)用窮舉組合，動態(tài)規(guī)劃窮舉組合，適用于相鄰元素有規(guī)律。處注意邊界值的情況。不能有重復(fù)，遺漏。 題目解讀： 窮舉列出所有二叉樹的結(jié)構(gòu)類型。重點： 動態(tài)規(guī)劃，關(guān)注臨近root，left，right之間的關(guān)系應(yī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)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...
閱讀 2736·2021-11-18 10:02
閱讀 2777·2021-11-15 11:38
閱讀 3853·2021-11-12 10:36
閱讀 805·2021-11-12 10:34
閱讀 3023·2021-10-21 09:38
閱讀 1627·2021-09-29 09:48
閱讀 1744·2021-09-29 09:34
閱讀 1204·2021-09-22 10:02
