[LeetCode] Unique Binary Search Trees
LeetCode search Binary unique Trees
2023-09-11 14:17:25 时间
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
Tree Dynamic Programming
思路：dp
如果集合为空，只有一种BST，即空树，
UniqueTrees[0] =1
如果集合仅有一个元素，只有一种BST，即为单个节点UniqueTrees[1] = 1
UniqueTrees[2] = UniqueTrees[0] * UniqueTrees[1] (1为根的情况)+ UniqueTrees[1] * UniqueTrees[0] (2为根的情况）。
再看一遍三个元素的数组，可以发现BST的取值方式如下：
UniqueTrees[3] = UniqueTrees[0]*UniqueTrees[2] (1为根的情况)
+ UniqueTrees[1]*UniqueTrees[1] (2为根的情况)
+ UniqueTrees[2]*UniqueTrees[0] (3为根的情况)
所以，由此观察，可以得出UniqueTrees的递推公式为UniqueTrees[i] = ∑ UniqueTrees[0...k] * [i-1-k] k取值范围 0<= k <=(i-1)
class Solution { public: int numTrees(int n) { int *num = new int[n+1]; num[0] = 1; num[1] = 1; int tmp = 0; for(int i =2; i <=n; i++) { tmp = 0; for(int j= 0; j <i ;j++) tmp += num[j]*num[i-j-1]; num[i] = tmp; } tmp = num[n]; delete []num; return tmp; } };
相关文章
- Leetcode: Lowest Common Ancestor of a Binary Search Tree
- Leetcode: Word Search II
- Leetcode: Validate Binary Search Tree
- Leetcode: Recover Binary Search Tree
- Leetcode: Convert Sorted List to Binary Search Tree
- Leetcode: Unique Binary Search Trees II
- Leetcode Validate Binary Search Tree
- leetcode 二分查找 Search in Rotated Sorted Array
- Binary Search Tree 以及一道 LeetCode 题目
- [LeetCode] Unique Binary Search Trees II
- [LeetCode] Word Search
- [LeetCode] Search for a Range
- 【LeetCode】96. Unique Binary Search Trees (2 solutions)
- 【LeetCode】99. Recover Binary Search Tree
- 【LeetCode】74. Search a 2D Matrix
- 【LeetCode】109. Convert Sorted List to Binary Search Tree
- 【LeetCode】79. Word Search
- LeetCode——Convert Sorted Array to Binary Search Tree
- Unique Binary Search Trees -- LeetCode
- [LeetCode] Binary Search 二分搜索法
- [LeetCode] Insert into a Binary Search Tree 二叉搜索树中插入结点
- [LeetCode] Find Mode in Binary Search Tree 找二分搜索数的众数
- [LeetCode] 255. Verify Preorder Sequence in Binary Search Tree 验证二叉搜索树的先序序列
- [LeetCode] Add and Search Word - Data structure design 添加和查找单词-数据结构设计
- [LeetCode] 81. Search in Rotated Sorted Array II 在旋转有序数组中搜索之二
- [LeetCode] 96. Unique Binary Search Trees 独一无二的二叉搜索树
- [LeetCode] Convert Sorted List to Binary Search Tree 将有序链表转为二叉搜索树
- leetcode 637. Average of Levels in Binary Tree 二叉树的层平均值(简单)