Unique Binary Search Trees问题

Fri Oct 09 17:31:19 CST 2015 667 算法

文章摘要来自LeetCode的题目,传入一个整数n,求n个结点可以组成(分别存储数值1...n)有多少棵不同的二叉树

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

Problem from leetcode.


大概思路:当n为0时,为空树,结果为1;当n为1时,只有根节点,结果为1;因此有nums[0]=1,nums[1]=1;当n为2时,有两种摆法:1为根结点和2为根结点;因此nums[2]=2;

当n为3时,若选择1为根结点,则左子树有nums[0]个摆法,右子树有nums[2]个摆法;若选择2为根结点,则左子树有nums[1]种摆法,右子树有nums[1]种摆法;若选择3为根结点,则左子树有nums[2]个摆法,右子树有nums[0]个摆法。因此可得到递推关系式nums[n]=∑nums[k]+nums[n-1-k],其中k取值范围为[0,n-1],这里的-1是因为要有一个放在根结点。


public class Solution {
    public int numTrees(int n) {
        int nums[] = new int[n+1];    //开辟n+1大小的int数组,因为我们要利用到下标n
        nums[0] = 1;                  //显然的
        nums[1] = 1;                  //显然的
        for(int i=2; i<n+1; i++){     //从数组下标为2开始填充数组,直到我们需要的结果n
            for(int j=0; j<i; j++){   //j为放在左子树的结点个数,j最大值为i-1,i-1-j为放在右子树的结点个数。
                nums[i] += nums[j]*nums[i-1-j];
            }
        }
        return nums[n];               //返回我们的结果
    }
}


打赏
打赏

分享到: