微信搜一搜：bigsai
算法文章題解全部收錄在github倉庫bigsai-algorithm
關(guān)注回復(fù)進(jìn)群即可加入力扣打卡群，歡迎劃水。近期打卡：
LeetCode 92反轉(zhuǎn)鏈表Ⅱ&93復(fù)制ip地址&94二叉樹的中序遍歷
LeetCode 90子集Ⅱ&91解碼方法
LeetCode 88合并兩個有序數(shù)組&89格雷編碼

96 不同的二叉搜索樹Ⅱ

給定一個整數(shù) n，求以 1 … n 為節(jié)點(diǎn)組成的二叉搜索樹有多少種？

示例:

輸入: 3 輸出: 5 解釋: 給定 n = 3, 一共有 5 種不同結(jié)構(gòu)的二叉搜索樹:1 3 3 2 1\ / / / \ \3 2 1 1 3 2/ / \ \2 1 2 3

分析
首先弄清這棵樹是一顆二叉搜索樹。大的節(jié)點(diǎn)只能在右側(cè)，小的在左側(cè)。所以n個節(jié)點(diǎn)如果以第i為節(jié)點(diǎn)，那么[1-i-1]的都在左側(cè)，[i+1,n]都在右側(cè)。

如果單單從結(jié)構(gòu)上考慮那么就是：

左側(cè)0個數(shù)量 x 右側(cè)n-1個數(shù)量
左側(cè)1個數(shù)量 x 右側(cè)n-2個數(shù)量
左側(cè)2個數(shù)量 x 右側(cè)n-3個數(shù)量
……
左側(cè)n-1個數(shù)量 x 右側(cè)0個數(shù)量

所以這個題父子關(guān)系很大，從上就能得到這樣的遞推，當(dāng)然這題我們使用動態(tài)規(guī)劃來解決，dp[i]表示i個節(jié)點(diǎn)所有可以排列的數(shù)量。就得到狀態(tài)轉(zhuǎn)移方程：

dp[i]=sum(dp[j]*dp[i-j-1]) j∈[0,i） （左右子節(jié)點(diǎn)之和為i-1）

實(shí)現(xiàn)代碼為：

class Solution {public int numTrees(int n) {if(n<2)return n;int dp[]=new int [n+1];dp[0]=1;dp[1]=1;for(int i=2;i<n+1;i++){for(int j=0;j<i;j++){dp[i]+=dp[j]*dp[i-j-1];}}return dp[n];} }

95不同的二叉搜索樹Ⅱ

給定一個整數(shù) n，生成所有由 1 … n 為節(jié)點(diǎn)所組成的 二叉搜索樹 。

示例：

輸入：3 輸出： [[1,null,3,2],[3,2,null,1],[3,1,null,null,2],[2,1,3],[1,null,2,null,3] ] 解釋： 以上的輸出對應(yīng)以下 5 種不同結(jié)構(gòu)的二叉搜索樹：1 3 3 2 1\ / / / \ \3 2 1 1 3 2/ / \ \2 1 2 3提示：0 <= n <= 8

分析
這題和上一題不一樣，要求我們返回所有可能的這么一個樹，這題的話我還是使用遞歸的方式，當(dāng)然不可以無腦遞歸然后去構(gòu)造這棵樹因?yàn)榭赡軙兄貜?fù)比如 2 3 1 和 2 1 3這個序列構(gòu)成樹的結(jié)果是一致的。

所以要考慮一個沒有重復(fù)但能全部覆蓋的策略。這題和上一題有一些不一樣的地方就是上一題通過dp可能很多連續(xù)數(shù)不同但是結(jié)構(gòu)相同我們可以不計(jì)算，但這里面每一種情況都需要構(gòu)建。

所以這題怎么考慮呢？和上題一樣，對于n個節(jié)點(diǎn)，我們需要考慮的其實(shí)就是n個節(jié)點(diǎn)每個為根節(jié)點(diǎn)的構(gòu)造可能性。單獨(dú)考慮第i個節(jié)點(diǎn)，第i個節(jié)點(diǎn)的left和right分別對應(yīng)一個節(jié)點(diǎn)。所以要找到這種節(jié)點(diǎn)組合的排列可能。

在具體實(shí)現(xiàn)上我們借助一個遞歸函數(shù)generateTrees(int start, int end)表示從start到end的所有滿足條件的節(jié)點(diǎn)。而在這個遞歸調(diào)用的過程中，我們循環(huán)遞歸分別獲取根為第1,2,3……n個節(jié)點(diǎn)的組成情況(遞歸調(diào)用獲取左右部分節(jié)點(diǎn)然后新建節(jié)點(diǎn)左右部分)。

具體代碼為：

public List<TreeNode> generateTrees(int n) {if(n==0)return new ArrayList<TreeNode>();return generateTrees(1,n); } private List<TreeNode> generateTrees(int start, int end) {// TODO Auto-generated method stubList<TreeNode> allList=new ArrayList<TreeNode>();//返回start-end的所有可能的節(jié)點(diǎn)if(start>end)//要有null{allList.add(null);return allList;}for(int i=start;i<=end;i++){List<TreeNode>leftNodes=generateTrees(start,i-1);//左側(cè)List<TreeNode>rightNodes=generateTrees(i+1,end);//右側(cè)for(TreeNode lnode:leftNodes){for(TreeNode rNode:rightNodes)//進(jìn)行組合{TreeNode node=new TreeNode(i);node.left=lnode;node.right=rNode;allList.add(node);//創(chuàng)建新節(jié)點(diǎn)添加到集合中}}}return allList; }

原創(chuàng)不易，bigsai請你幫兩件事幫忙一下:

star支持一下， 您的肯定是我在平臺創(chuàng)作的源源動力。

微信搜索「bigsai」，關(guān)注我的公眾號，不僅免費(fèi)送你電子書，我還會第一時間在公眾號分享知識技術(shù)。加我還可拉你進(jìn)力扣打卡群一起打卡LeetCode。

記得關(guān)注、咱們下次再見！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 96不同的二叉搜索树95不同的二叉搜索树Ⅱ的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。