本文共 1625 字,大约阅读时间需要 5 分钟。
题目链接:https://leetcode.com/problems/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.
1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
思路: 可以用记忆化搜索, 即当我们以一个数为根节点的时候, 问题就分割成了左右两个子集, 然后再继续解决子问题合并成当前问题的解. 如果直接搜索会有很多重复的解, 因此可以边搜索边记录.
代码如下:
class Solution {public: int numTrees(int n) { if(n <= 1) return 1; if(hash.count(n)) return hash[n]; int cnt = 0; for(int i = 1; i<= n; i++) { int left = numTrees(i-1), right = numTrees(n-i); hash[i-1] = left, hash[n-i] = right; cnt += left*right; } hash[n] = cnt; return cnt; }private: unordered_maphash;};
这样问题还可以转化成动态规划的问题. 可以看到这是一个中序有序的二叉树,根据二叉搜索树的性质,一个节点左子树值都要比本身小,右子树节点值都比本身大。以一个节点为根能产生的有效的树的数量由左右子树的数量决定,即假设左子树数量为a,右子树数量为b,则以此节点为根的树的数量为a*b。对于一个n,从1 - n均可作为结点,因此把从1-n作为结点产生的树的数量相加即可得到n的所有子树的数量。状态转移方程为:dp[n] = sum(dp[i-1] * dp[n-i]), 1 <= i <= n。
具体代码如下:
class Solution {public: int numTrees(int n) { vector dp(n+1); dp[0] = dp[1] = 1; for(int i = 2; i<= n; i++) { for(int j = 1; j<= i; j++) { int cnt = dp[j-1]*dp[i-j];//以j为根,节点总数为i能产生的子树数量 dp[i] += cnt; } } return dp[n]; }};
参考:https://siddontang.gitbooks.io/leetcode-solution/content/dynamic_programming/unique_binary_search_trees.html
转载地址:http://rilbn.baihongyu.com/