【題目】

Given?n, how many structurally unique?BST's?(binary search trees) that store values 1...n?

For example,
Given?n?= 3, there are a total of 5 unique BST's.

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

【題意】

? ? 給定一個數字n, 問用1,2,3,4,5...n這n個值，能構造多少棵合法的二叉搜索樹

【思路】

? ? 對于給定[1,n]區間，先確定全部可能的根。如果根為k, 則該二叉樹左子樹的取值區間為[1, k-1]和右子樹的取值區間[k+1, n]。
? ? 而二叉搜索搜索樹的隨意一個節點的左右子樹也是二叉搜索樹，因此我們須要確定[1,k-1]和[k+1, n]上構造的二叉搜索樹的數目, 比方分別為left[k], right[k]。

則以k的根的二叉搜索樹的數目即為，left[k]*right[k]
? ??
? ? 本題用遞歸來解決。

【代碼】

class Solution { public:int binaryTreeNums(int start, int end){//[start, end]區間上構造二叉樹的數目if(start>=end)return 1; //start<end表示空子樹， start==end表示葉子節點int treeNums=0;for(int root=start; root<=end; root++){int leftCount = binaryTreeNums(start, root-1); //計算左子樹的數目int rightCount = binaryTreeNums(root+1, end); //計算右子樹的數目treeNums+= leftCount*rightCount;}return treeNums;}int numTrees(int n) {if(n==0)return 0;return binaryTreeNums(1, n);} };

轉載于:https://www.cnblogs.com/mengfanrong/p/5152210.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的LeetCode: Unique Binary Search Trees [095]的全部內容，希望文章能夠幫你解決所遇到的問題。

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