Unique Binary Search Tree@leetcode

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career

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

» Solve this problem

此题刚开始看上去无从下手，但是稍作分析就会发现，比较简单。简单在于它不用我们输出所有的 BST，而仅仅是给出有多少个就可以了。这样我们可以一个一个当作root看子树的个数。这时候就是recursion and dp了。这个时候又注意到，当结点i当root时，所有小于i的，会在左子树，所有大于i的，会在右子树。就是个简单的递归了。

	class Solution {
	public:
	int numTrees(int n) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	if(n==0) return 0;
	if(n==1) return 1;
	int res=0;
	for(int i=1;i<=n;i++)
	{
	int l=numTrees(i-1);
	int r=numTrees(n-i);
	if(!l)
	res+=r;
	else if(!r)
	res+=l;
	else if(l&&r)
	res+=l*r;
	}
	return res;
	}
	};

view raw Unique Binary Search Tree I hosted with ❤ by GitHub

更简单的逻辑．

	class Solution {
	public:
	int numTrees(int n) {
	if(n == 1 || n == 0) return 1;
	if(n == 2) return 2;
	int res = 0;
	for(int i = 1; i<=n; i++){
	res+= numTrees(i-1)*numTrees(n-i);
	}
	return res;
	}
	};

view raw unique binary search tree hosted with ❤ by GitHub