首页 > 代码库 > 【LeetCode】96. Unique Binary Search Trees-唯一二叉排序树的个数

【LeetCode】96. Unique Binary Search Trees-唯一二叉排序树的个数

一、描述:

技术分享

二、思路:

BST(二叉排序树):中序遍历的结果为非递减序列,并且节点(个数和值)相同的不同二叉树的中序遍历结果都相同;

当左子树的节点个数确定后,右子树的个数也随之确定;

当节点个数为0或1时,二叉树只有1种,表示为f(0)=1,f(1)=f(0)*f(0);

当节点个数为2时,总的种类数=左子树为空f(0)*右子树不为空f(1)+左子树不为空f(1)*右子树为空f(0),即f(0)*f(1)+f(1)*f(0)=2种;

当节点个数为3时,有左子树为空f(0)*右子树不为空f(2)+左子树不为空f(2)*右子树为空f(0)+左右子树均不为空f(1)*f(1),即f(0)*f(2)+f(2)*f(0)+f(1)*f(1)=1*2+2*1+1*1=5种;

……

当节点个数为n时,结果为f(0)*f(n-1)+f(1)*f(n-2)+……+f(n-2)*f(1)+f(n-1)*f(0);

由上边规律可以得出,当节点个数n大于0时,n对应的不同二叉树种类数总是依赖n等于0—(n-1)时对应的值才得到的,故可以将0—(n-1)个值对应的二叉树个数保存到一个HashMap<K,V>集合中,递归调用时只需要从集合中获取对应值即可;

有没有觉得和Fibonacci数列很像,原理相同。

三、代码:

public class Solution {
    public int numTrees(int n) {
        if(n==0 || n==1){
            return 1;
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0, 1);
        map.put(1, 1);
        for(int i=2;i<=n;i++){
            int count = 0;
            for(int j=0;j<i;j++){
                count += map.get(j)*map.get(i-j-1);//减1是除过根节点
            }
            map.put(i, count);
        }
        return map.get(n);//n对应的树的个数
    }
}

 

【LeetCode】96. Unique Binary Search Trees-唯一二叉排序树的个数