不同的二叉搜索樹2
題目：給定一個整數 n，生成所有由 1 ... n 為節(jié)點所組成的二叉搜索樹。
示例:
輸入: 3
輸出:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
題目截圖
思路：其實這個題感覺又是個回溯啊。。首先選擇第一個元素，然后因為是搜索二叉樹，所以遵循左小右大。感覺上比較麻煩，我先去實現下看看
做完回來了，這個題怎么說呢，不是一個回溯問題，之前是我想復雜了。其實不用回溯。但是原理上是類似的。回溯是指添加，遞歸，然后退回上一步。而這道題好一點的是沒有一個list可以專門用來存儲是否添加過某元素了。而是因為數字是確定好的范圍的，所以可以直接用當前值前面，當前值后面來自動判斷左右樹。剛說有點類似回溯的也是這點。每一個值都可能是跟節(jié)點，所以要每一種情況都走一次遞歸。同樣其實子樹的節(jié)點也都是每一個值都有可能。所以還是遞歸套遞歸。我感覺我表達能力是個大問題，可能沒說明白。我直接貼代碼：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<TreeNode> generateTrees(int n) {
if(n==0) return new ArrayList<TreeNode>();
return dfs(1,n);
}
public List<TreeNode> dfs(int start,int end){
List<TreeNode> res = new ArrayList<TreeNode>();
if(start>end){
res.add(null);
return res;
}
for(int i = start;i<=end;i++){
List<TreeNode> left = dfs(start,i-1);
List<TreeNode> right = dfs(i+1,end);
for(TreeNode subLeft :left){
for(TreeNode subRight:right){
TreeNode node =new TreeNode(i);
node.left = subLeft;
node.right = subRight;
res.add(node);
}
}
}
return res;
}
}
簡單說兩句，重點是dfs方法中的for循環(huán)，第一層for循環(huán)，是把當前i作為根節(jié)點，然后找出左子樹的所有可能性和右子樹的所有可能性。這塊就用到了遞歸，因為左子樹和右子數作為單獨的樹，其實也是要遍歷確定子樹的“根節(jié)點”的。最后雙層for循環(huán)可以把所有子樹的可能情況都考慮到。反正情況就是這樣。
剛剛看了性能排行第一的代碼，就是多了點判斷，我貼出來參考下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<TreeNode> generateTrees(int n) {
List<TreeNode> ans=new ArrayList<TreeNode>();
if(n==0) return ans;
return getAns(1,n);
}
public List<TreeNode> getAns(int start,int end){
List<TreeNode> ans=new ArrayList<TreeNode>();
if(start>end){
//沒有數字的時候返回n
ans.add(null);
return ans;
}
if(start==end){
//只有一個數字的時候直接加入
TreeNode tree=new TreeNode(start);
ans.add(tree);
return ans;
}
for(int i=start;i<=end;i++){
//得到所有的左子樹和右子樹
List<TreeNode> leftTrees=getAns(start,i-1);
List<TreeNode> rightTrees=getAns(i+1,end);
for(TreeNode leftTree:leftTrees){
//分別進行組合，將其分別連接到root兩側
for(TreeNode rightTree:rightTrees){
TreeNode root=new TreeNode(i);
root.left=leftTree;
root.right=rightTree;
ans.add(root);
}
}
}
return ans;
}
}
然后只要理解了就簡單，我反正一開始陷入了回溯的牛角尖，琢磨半天也沒寫出來，后來靈機一動才摸索出來了。這道題只要思路對了代碼不難，然后就這樣了，直接下一題。
不同的二叉搜索樹
題目：給定一個整數 n，求以 1 ... n 為節(jié)點組成的二叉搜索樹有多少種？
示例:
輸入: 3
輸出: 5
解釋:
給定 n = 3, 一共有 5 種不同結構的二叉搜索樹:
題目截圖
思路：說真的，這兩道題有毛病吧？哪怕都出了也應該這個1在前面啊，我都做出2了還有必要做1？？？？就是上面的代碼，返回值是res.size()就好了。我去粘貼提交下。好像不太多，我看題目，這個連樹的結構都莫有了，，，貌似這個種類應該是有簡單算法的。直接可以拋出樹的結構直接數字相加，，我還是去試試代碼吧。
很好，超時了。。。但是我確信我的代碼沒問題。。哈哈，先附上截圖吧：
然后為什么超時。。。我不知道啊，還有什么更簡單的算法么？我現在明白為啥2放在1前面了，都是套路啊。。哎。這道題感覺考點都變了，我再尋思尋思。
唔，我這里用的遞歸，問題應該就出在這里，遞歸超時，有一種遞歸的高效版：動態(tài)規(guī)劃——用數組記錄中間過程的遞歸。
我記得時間復雜度是n方 和n的區(qū)別。我去試試這道題用動歸怎么解。而且我覺得這道題確實這么做是有問題的，因為 比如說三個節(jié)點能組成的方式是固定的。所以如果前面三個后面三個，只算一次就ok了，而我這段代碼是要重復算的，這個是受了上一道題的影響，這里不需要列出來怎么排列，我從頭開始想想怎么做吧。
好了，果然是dp問題，我直接貼代碼：
class Solution {
public int numTrees(int n) {
if(n<=1) return n;
//幾個元素能組成多少中選擇的字典
int[] d = new int[n+1];
//沒有元素或只有一個元素只有1中可能，
d[0] = 1;
d[1] = 1;
for(int i = 2;i<=n;i++){
//以j為根節(jié)點，求出i個元素有多少種排列
//這里只是計數，從0開始則小于i，從1開始小于等于i
for(int j = 0;j<i;j++){
//因為j是從0開始，所以j直接代表下標（從1開始要j-1。同理后面是i-j）
d[i] += d[j]*d[i-j-1];
}
}
return d[n];
}
}
因為這個題我沒啥思路，是一點點測試理解的，所以注釋我感覺寫的比較清楚了。。沒啥可講的。就是一個用數組記錄中間過程的遞歸。如果看不懂這個或者說不太明白，建議去補習動態(tài)規(guī)劃的知識。下一題了。
驗證二叉搜索樹
題目：給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。
假設一個二叉搜索樹具有如下特征：
節(jié)點的左子樹只包含小于當前節(jié)點的數。
節(jié)點的右子樹只包含大于當前節(jié)點的數。
所有左子樹和右子樹自身必須也是二叉搜索樹。
思路：這道題有點送分啊。。。感覺做過類似的呢，，我有個大膽的想法。前序遍歷，結果不是遞增就是false。。不知道想法對不對呢。我去試試。
哈哈哈哈，我這個大膽的想法就這么實現了，有點意思啊。。。
我直接貼出第一版本的代碼：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
test(root,list);
for(int i = 0;i<list.size()-1;i++){
if(list.get(i+1)<=list.get(i)) return false;
}
return true;
}
public void test(TreeNode root,List<Integer> list){
if(root==null) return;
test(root.left,list);
list.add(root.val);
test(root.right,list);
}
}
講真，leetcode中中等難度最簡單的題目，沒有之一。
然后這個性能不是很好，因為我本來只是想嘗試下思路對不對，，估計是可以優(yōu)化的，我目前想到的優(yōu)化點就是不用遍歷完二叉樹再判斷了，可以在遍歷的時候就判斷。新加元素小于等于前一個元素，直接false。。我去處理下。
emmmm....怎么說呢，改是改完了，運行也對了，就是性能還是2ms，一點沒長進。。。我還是把代碼貼上來吧，也算是個思路 ：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<Integer> list;
public boolean isValidBST(TreeNode root) {
list = new ArrayList<Integer>();
return test(root);
}
public boolean test(TreeNode root){
if(root==null) return true;
boolean l = test(root.left);
if(list.size()!=0 && root.val<= list.get(list.size()-1)) return false;
list.add(root.val);
boolean r = test(root.right);
return l && r;
}
}
感覺憑我一己之力已經難以優(yōu)化了，我直接去看性能排行第一的代碼吧。
我直接貼代碼：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
return isBST(root,Long.MIN_VALUE,Long.MAX_VALUE);
}
public boolean isBST(TreeNode node,long min,long max){
if(node==null){
return true;
}
if(node.val<=min||node.val>=max){
return false;
}
return isBST(node.left,min,node.val)&&isBST(node.right,node.val,max);
}
}
差不多就是遍歷過程中判斷，只不過我用了list，人家沒用。。。我感覺我是受了第一個遍歷完判斷的思路的影響。。?？戳巳思业拇a恍然大悟豁然開朗，我覺得我也應該能想出來啊。。。哎
思路：然后今天的筆記就記到這里，如果稍微幫到你了記得點個喜歡點個關注！打算從今天開始正常刷題啦，反正閑著也是閑著。也祝大家工作順順利利！生活平平安安健健康康！
