Voyz's Studio.

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

字数统计: 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:

1
2
3
4
5
6
7
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* @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);
};
CATALOG
  1. 1. LeetCode算法笔记–Day48
    1. 1.1. 题目1:
      1. 1.1.1. 96. Unique Binary Search Trees
      2. 1.1.2. Concept:
        1. 1.1.2.1. 二叉搜索树(BST)
      3. 1.1.3. Analyse:
      4. 1.1.4. My Answer: