微信搜一搜：
bigsai
演算法文章題解全部收錄在github倉庫bigsai-algorithm
關注回復進群即可加入力扣打卡群，歡迎劃水，近期打卡：
LeetCode 92反轉鏈表Ⅱ&93復制ip地址&94二叉樹的中序遍歷
LeetCode 90子集Ⅱ&91解碼方法
LeetCode 88合并兩個有序陣列&89格雷編碼
96 不同的二叉搜索樹Ⅱ
給定一個整數 n，求以 1 … n 為節點組成的二叉搜索樹有多少種？
示例:
輸入: 3
輸出: 5
解釋:
給定 n = 3, 一共有 5 種不同結構的二叉搜索樹:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
分析
首先弄清這棵樹是一顆二叉搜索樹，大的節點只能在右側，小的在左側，所以n個節點如果以第i為節點，那么[1-i-1]的都在左側，[i+1,n]都在右側，
如果單單從結構上考慮那么就是：
左側0個數量 x 右側n-1個數量
左側1個數量 x 右側n-2個數量
左側2個數量 x 右側n-3個數量
……
左側n-1個數量 x 右側0個數量
所以這個題父子關系很大，從上就能得到這樣的遞推，當然這題我們使用動態規劃來解決，dp[i]表示i個節點所有可以排列的數量，就得到狀態轉移方程：
dp[i]=sum(dp[j]*dp[i-j-1]) j∈[0,i）（左右子節點之和為i-1）
實作代碼為：
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不同的二叉搜索樹Ⅱ
給定一個整數 n，生成所有由 1 … n 為節點所組成的 二叉搜索樹 ，
示例：
輸入：3
輸出：
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解釋：
以上的輸出對應以下 5 種不同結構的二叉搜索樹：
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
提示：
0 <= n <= 8
分析
這題和上一題不一樣，要求我們回傳所有可能的這么一個樹，這題的話我還是使用遞回的方式，當然不可以無腦遞回然后去構造這棵樹因為可能會有重復比如 2 3 1 和 2 1 3這個序列構成樹的結果是一致的，
所以要考慮一個沒有重復但能全部覆寫的策略，這題和上一題有一些不一樣的地方就是上一題通過dp可能很多連續數不同但是結構相同我們可以不計算，但這里面每一種情況都需要構建，
所以這題怎么考慮呢？和上題一樣，對于n個節點，我們需要考慮的其實就是n個節點每個為根節點的構造可能性，單獨考慮第i個節點，第i個節點的left和right分別對應一個節點，所以要找到這種節點組合的排列可能，
在具體實作上我們借助一個遞回函式generateTrees(int start, int end)表示從start到end的所有滿足條件的節點，而在這個遞回呼叫的程序中，我們回圈遞回分別獲取根為第1,2,3……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 stub
List<TreeNode> allList=new ArrayList<TreeNode>();//回傳start-end的所有可能的節點
if(start>end)//要有null
{
allList.add(null);
return allList;
}
for(int i=start;i<=end;i++)
{
List<TreeNode>leftNodes=generateTrees(start,i-1);//左側
List<TreeNode>rightNodes=generateTrees(i+1,end);//右側
for(TreeNode lnode:leftNodes)
{
for(TreeNode rNode:rightNodes)//進行組合
{
TreeNode node=new TreeNode(i);
node.left=lnode;
node.right=rNode;
allList.add(node);//創建新節點添加到集合中
}
}
}
return allList;
}
原創不易，bigsai請你幫兩件事幫忙一下:
-
star支持一下， 您的肯定是我在平臺創作的源源動力，
-
微信搜索「bigsai」，關注我的公眾號，不僅免費送你電子書，我還會第一時間在公眾號分享知識技術，加我還可拉你進力扣打卡群一起打卡LeetCode，
記得關注、咱們下次再見！
CSDN認證博客專家
資料結構與演算法
爬蟲
Java
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/244321.html
標籤：其他