LeetCode算法笔记--不同的二叉搜索树

算法题热题HOT100 二叉树

字数统计: 604阅读时长: 2 min

 2020/12/21   Share

LeetCode算法笔记–Day48

题目1：

96. Unique Binary Search Trees

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

Note: The solution set must not contain duplicate subsets.

example
input: 3
output: 5

Explanation:

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

Concept:

二叉搜索树(BST)

所有左儿子的数字都比爸爸数字小，所有右儿子的数字都比爸爸数字大的二叉树。
每个爸爸节点分出来的左边部分里，任何一个数字都比这个爸爸数字小；右边部分里，任何一个数字都比这个爸爸数字大。
从最顶上的父节点开始，每次问我，“你想的数字比当前节点大还是小？”，你就可以一步步顺着树往下走，搜索到我心里想的数字。所以这就是一个搜索的过程，是一个不断缩小搜索范围的过程。

Analyse:

从1,2,…n数列构建搜索树，实际上只是一个不断细分的过程。例如用[1,2,3,4,5,6]构建，”2”作为树根，[1]为左子树，[3,4,5,6]为右子树。就变成了一个更小的问题：如何用[3,4,5,6]构建搜索树？比如，我们可以提起”5”作为树根，[3,4]是左子树，[6]是右子树。
我们来看[1,2,3]
如果提起1作为树根，左边有f(0)种情况，右边f(2)种情况，左右搭配一共有f(0)f(2)种情况
如果提起2作为树根，左边有f(1)种情况，右边f(1)种情况，左右搭配一共有f(1)f(1)种情况
如果提起3作为树根，左边有f(2)种情况，右边f(0)种情况，左右搭配一共有f(2)f(0)种情况
容易得知f(3) = f(0)f(2) + f(1)f(1) + f(2)f(0)
同理
f(4) = f(0)f(3) + f(1)f(2) + f(2)f(1) + f(3)f(0)
f(5) = f(0)f(4) + f(1)f(3) + f(2)f(2) + f(3)f(1) + f(4)*f(0)
已知f(0) = 1, f(1) = 1

My Answer：

/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
    let fn = (_n)=>{
        let res = 0;
        if(_n == 0 || _n == 1) return 1;
        for(let i=0;i<_n>>1;i++){
            res += 2*fn(i)*fn(_n-1-i);
        }
        if(_n%2 == 1) res += fn(_n>>1)*fn(_n>>1);
        return res;
    }
    return fn(n);
};

Next Post

ES11--2020年JavaScript的新特性
Previous Post

LeetCode算法笔记--二叉树的中序遍历

CATALOG

1. LeetCode算法笔记–Day48
1. 1.1. 题目1：

