2019-04-15  235 views 评论

[leetcode]unique binary search trees

 标签:

题目描述

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.

题目解析

我们可以发现,只需求出左、右子树各有多少种,二者相乘即为以 i 作为root时BST的总数。所以我们可以用动态规划来实现。当节点数为0个的时候,子树为0个,节点为1个的时候,子树为1个,节点数为2个的时候,子树为2个。当n>=3的时候,左右子树种类之积就是结果。所以我们只需要由下至上求解即可。

代码实现

给我留言

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: