/*這道題的關鍵是：動態表盡量的選取，知道二叉搜索樹中左子樹的點都比根節點小，右子樹的點都比根節點大所以當i為根節點，左子樹有i-1個點，右子樹有n-i個點，左右子樹就可以開始遞歸構建，過程和一開始的過程是一樣的，而左右子樹的特征中可以知道的就是點的個數，所以用點的個數作為動態變量就很好。這樣就給我們提供了一個思路：動態規劃和樹結合的題，由于子問題就是左右樹，所以動態變量的選取基本就是考慮題目給出的信息中，可以從根節點得到左右子樹的哪些特征，用這個特征作為動態變量。二叉搜索樹中，都是左子樹的點小于根節點，右子樹的點大于根節點，對于所有子樹都是這樣。用dp[i]表示有i個數的時候能組成多少樹dp[i] = dp[0]*dp[i-1]+ ...+ dp[i-1]*dp[0]等號右邊分別代表1到i分別是根節點的情況*/int[] dp = new int[n+1];dp[0] = 1;//當沒有節點時，就只有一種情況for (int i = 1; i < n+1; i++) {for (int j = 0; j < i; j++) {dp[i] += dp[j] * dp[i-j-1];}}return dp[n];

?

1 public List<TreeNode> generateTrees(int n) { 2 /* 3 從i到n依次選取做為根節點，生成一棵樹.根節點為i的這個過程我們叫做function(i)，則function（i）中左子樹就是從1到i-1的 4 生成過程，右子樹就是從i+1到n的過程，遞歸function就行，然后對左右子樹就行全匹配就行 5 */ 6 if (n < 1) 7 return new ArrayList<TreeNode>(); 8 return build(1, n); 9 } 10 11 public List<TreeNode> build(int start, int end) { 12 List<TreeNode> res = new ArrayList<>(); 13 if (start > end) 14 { 15 res.add(null); 16 return res; 17 } 18 for (int i = start; i <= end; i++) { 19 List<TreeNode> left = build(start, i - 1); 20 List<TreeNode> right = build(i + 1, end); 21 22 for (TreeNode lt : 23 left) { 24 for (TreeNode rt : 25 right) { 26 //由于每次組合都形成一個新的樹，所以新建樹應該是在這里 27 TreeNode root = new TreeNode(i); 28 root.left = lt; 29 root.right = rt; 30 //注意添加的位置，每組合一個左右子樹就會形成一種情況 31 res.add(root); 32 } 33 } 34 35 } 36 return res; 37 }

?

轉載于:https://www.cnblogs.com/stAr-1/p/7922877.html

總結

以上是生活随笔為你收集整理的96. Unique Binary Search Trees1和2的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。