問題描寫敘述：

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

解題思路：分別考慮由1-n作為根節(jié)點(diǎn)。當(dāng)以i作為跟節(jié)點(diǎn)時(shí)。其左子樹節(jié)點(diǎn)數(shù)為i-1。右子樹的節(jié)點(diǎn)數(shù)為n-i。以相同的方法遞歸地求左子樹和右子樹可能形成的二分查找樹的個(gè)數(shù)為leftSubTree和rightSubTree。則以i做為根節(jié)點(diǎn)時(shí)所能形成的二分查找樹的個(gè)數(shù)為leftSubTree*rightSubTree。將各節(jié)點(diǎn)的leftSubTree*rightSubTree求和既得所求。

代碼：

public class Solution {public int numTrees(int n) {int sum = 0;int i;if(n == 0 || n == 1)return 1;for(i = 1;i <= n;i++){int leftSubTree = numTrees(i - 1);int rightSubTree = numTrees(n - i);sum = sum + leftSubTree * rightSubTree;}return sum;} }

轉(zhuǎn)載于:https://www.cnblogs.com/gcczhongduan/p/5081593.html

總結(jié)

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

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