不同的二叉查找樹I：

題目內(nèi)容：

給出 n，問由 1...n 為節(jié)點(diǎn)組成的不同的二叉查找樹有多少種？

樣例：

給出n = 3，有5種不同形態(tài)的二叉查找樹：

1 3 3 2 1\ / / / \ \3 2 1 1 3 2/ / \ \ 2 1 2 3

算法分析：

先來看一下二叉查找樹的特點(diǎn)，當(dāng)選定一個(gè)節(jié)點(diǎn)i作為中間節(jié)點(diǎn)時(shí)：

　　①位于該節(jié)點(diǎn)左子樹中的所有節(jié)點(diǎn)均小于i，假設(shè)該節(jié)點(diǎn)的左子樹的排列情況有m種；

　　②位于該節(jié)點(diǎn)右子樹中的所有節(jié)點(diǎn)均大于i，假設(shè)該節(jié)點(diǎn)的右子樹的排列情況有n種；

　　③綜合①和②，當(dāng)節(jié)點(diǎn)i作為當(dāng)前二叉查找樹的首節(jié)點(diǎn)時(shí)，該二叉查找樹的總排列數(shù)目有m*n；

因此對于一個(gè)擁有n個(gè)節(jié)點(diǎn)的二叉查找樹，其每一個(gè)節(jié)點(diǎn)均能成為某一二叉查找樹的首節(jié)點(diǎn)，因此動(dòng)態(tài)規(guī)劃的表達(dá)式為：

　　DP[i] = sum{ DP[j-1] * DP[i-j] }，其中1=< j <=i，DP[i]表示i個(gè)節(jié)點(diǎn)所能組成的二叉查找樹的數(shù)目；

代碼：　

public int numTrees(int n) {// write your code hereif(n==0)return 1;int[] result = new int[n+1];result[0]=1;result[1]=1;for(int i=2;i<=n;i++){for(int j=1;j<=i;j++){int left=result[j-1];int right=result[i-j];result[i]+=left*right;}}return result[n];}

不同的二叉查找樹II：

題目內(nèi)容：

給出n，生成所有由1...n為節(jié)點(diǎn)組成的不同的二叉查找樹；

樣例：

給出n = 3，有5種不同形態(tài)的二叉查找樹：

1 3 3 2 1\ / / / \ \3 2 1 1 3 2/ / \ \ 2 1 2 3

算法分析：

本題在 I 的基礎(chǔ)上要求返回的不是組數(shù)而是具體的組合，很明顯本題需要用遞歸的方式來解決問題，和 I 的思想基本一致，在遞歸的過程中找出所有的左右子樹的排列組合，然后分別連接到當(dāng)前節(jié)點(diǎn)的左子樹和右子樹，將結(jié)果作為當(dāng)前層的二叉查找樹的所有排列組合進(jìn)行返回。

代碼：

HashMap<String,List<TreeNode>> map = new HashMap<>();public List<TreeNode> findSolution(int begin, int end){List<TreeNode> result = new ArrayList<>();if(begin>end){result.add(null);return result;}if(begin==end){TreeNode temp = new TreeNode(begin);result.add(temp);return result;}String tag = String.valueOf(begin)+"-"+String.valueOf(end);if(map.get(tag)!=null){return map.get(tag);}for(int i=begin;i<=end;i++){List<TreeNode> left = findSolution(begin,i-1);List<TreeNode> right = findSolution(i+1,end);if(left.size()!=0&&right.size()!=0){for(TreeNode t1:left){for(TreeNode t2:right){TreeNode temp = new TreeNode(i);temp.left = t1;temp.right=t2;result.add(temp);}}}if(left.size()!=0&&right.size()==0){for(TreeNode t1:left){TreeNode temp = new TreeNode(i);temp.left = t1;result.add(temp);}}if(left.size()==0&&right.size()!=0){for(TreeNode t2:right){TreeNode temp = new TreeNode(i);temp.right = t2;result.add(temp);}}}map.put(tag,result);return result;}public List<TreeNode> generateTrees(int n) {// write your code heremap = new HashMap<>();return findSolution(1,n);/*long startTime=System.nanoTime();List<TreeNode> result = findSolution(1,n);long endTime=System.nanoTime();System.out.println("運(yùn)行時(shí)間為："+(endTime-startTime));return result;*/}

代碼中我還建立了一個(gè)map作為中間結(jié)果的記錄，用來降低一些重復(fù)區(qū)間段求解的時(shí)間開銷，其效果還是很明顯的，當(dāng)n=11時(shí)，沒有map的算法時(shí)間開銷為124313992ns，而有map的算法時(shí)間開銷為82106610ns；但是這題我我試了下即使不用map也能夠AC；

?

?

?

?

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/Revenent-Blog/p/7568627.html

總結(jié)

以上是生活随笔為你收集整理的LintCode刷题——不同的二叉查找树I、II的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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