请人建网站应注意什么,简单几步为wordpress加上留言板,建个网站怎么做推广,网站怎么集成支付宝题目来源 96. 不同的二叉搜索树
递归
1.我们要知道二叉搜索树的性质#xff0c;对于一个二叉搜索树#xff0c;其 【左边的节点值 中间的节点值 右边的节点值】#xff0c;也就是说#xff0c;对于一个二叉搜索树#xff0c;其中序遍历之后形成的数组应该是一…题目来源 96. 不同的二叉搜索树
递归
1.我们要知道二叉搜索树的性质对于一个二叉搜索树其 【左边的节点值 中间的节点值 右边的节点值】也就是说对于一个二叉搜索树其中序遍历之后形成的数组应该是一个递增的序列如下图 2.我们不妨就假设我们拿到了一个中序遍历的数组nums [1,2,3,4,5,6,7]来思考一个这样的数组能延伸出多少种二叉搜索树。 首先对于数组中的每一个元素都有可能成为二叉树最顶部的root节点例如上图中是nums[4]这个值即5充当了root节点。 3.还拿5这个节点为例即上图其左边有四个节点右边有两个节点。对于左边的四个节点假设能延伸出 n 种二叉搜索树子树对于右边的两个节点假设能延伸出 m 种二叉搜索树子树。则以5为root节点时的二叉搜索树总数为 m*n 4.这样我们遍历刚刚的nums数组以值i注意不是下标当做根节点其左边有i-1个节点右边有n-i个节点计算出可能的二叉搜索树数量添加到总结果里即可我们初步写出的代码如下
class Solution {public int numTrees(int n) {if(n 0 || n 1){return 1;}int count 0;for(int i 1;in;i){countnumTrees(i-1)*numTrees(n-i);}return count;}
}递归优化
其实是出现了很多次重复计算过程举例[1,2,3] 大量的重复计算造成我们时间过长因此我们可以用一个HashMap存储n和子树数量的映射如果已经计算过了当前n的子树数量直接取出用即可
class Solution {private HashMapInteger,Integer map new HashMap();public int numTrees(int n) {if(n 0 || n 1){return 1;}if(map.containsKey(n)){return map.get(n);}int count 0;for(int i 1;in;i){countnumTrees(i-1) * numTrees(n-i);map.put(n,count);}return count;}
}动态规划
动规五部曲
1.确定dp数组dp table以及下标的含义
dp[i] 1到i为节点组成的二叉搜索树的个数为dp[i]。 也可以理解是i个不同元素节点组成的二叉搜索树的个数为dp[i] 都是一样的。
2.确定递推公式
在上面的分析中其实已经看出其递推关系 dp[i] dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] j相当于是头结点的元素从1遍历到i为止。 所以递推公式dp[i] dp[j - 1] * dp[i - j]; j-1 为j为头结点左子树节点数量i-j 为以j为头结点右子树节点数量
3.dp数组如何初始化
初始化只需要初始化dp[0]就可以了推导的基础都是dp[0]。 那么dp[0]应该是多少呢 从定义上来讲空节点也是一棵二叉树也是一棵二叉搜索树这是可以说得通的。 从递归公式上来讲dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] 中以j为头结点左子树节点数量为0也需要dp[以j为头结点左子树节点数量] 1 否则乘法的结果就都变成0了。 所以初始化dp[0] 1
4.确定遍历顺序 首先一定是遍历节点数从递归公式dp[i] dp[j - 1] * dp[i - j]可以看出节点数为i的状态是依靠 i之前节点数的状态。 那么遍历i里面每一个数作为头结点的状态用j来遍历。 for(int i 1;i n;i){for(int j 1;ji;j){dp[i] dp[j-1]*dp[i-j];}}5.举例推导dp数组
n为5时候的dp数组状态如图 整体代码
class Solution {public int numTrees(int n) {int[] dp new int[n1];dp[0] 1;for(int i 1;i n;i){for(int j 1;ji;j){dp[i] dp[j-1]*dp[i-j];}}return dp[n];}
}
