[Leetcode] Unique Binary Search Trees 唯一二叉搜索树

enrecul101 发布于2019-08-14 12:38 / 988人阅读

摘要：而根可以选择从到的任意的数，唯一二叉树的总数，就是根为到的树相加。所以该问题化简为以为根，其唯一左子树和右子树各有多少，这就是个动态规划的问题了。

Unique Binary Search Trees I && II 解法请见：https://yanjia.li/zh/2019/02/...

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

动态规划 复杂度

时间 O(N!) 空间 O(N)

思路

二叉搜索树有个性质，就是左边的数都比根小，右边的数都比根大。另外，题目说明二叉树的节点是从1到n，所以我们能确定如果根为k，则根左边的数是1到k-1，根右边的数是k+1到n。还有一点技巧是，对于通过一个根来说，唯一二叉树的数量是其左子树的数量乘以右子树的数量，这是简单的乘法原理。并且，左右子树的形态数量是跟具体的数无关的，只跟这个树里有多少节点有关。而根可以选择从1到n的任意的数，唯一二叉树的总数，就是根为1到n的树相加。所以该问题化简为以k为根，其唯一左子树和右子树各有多少，这就是个动态规划的问题了。我们建立一个数组dp[i]，代表节点数为i的唯一子树有多少个。显然dp[0]=dp[1]=1。

代码

public class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 1;
        //从节点数2开始计算到节点数为n的BST
        for(int i = 2; i < n + 1; i++){
            //计算根是第一个数的BST数量，直到根是最后一个数的BST数量，这里j可以理解为根左边的节点数
            for(int j = 0; j < i; j++){
                //有n的节点的BST一共有 G(n)=F(1,n-1)+F(2,n-1)+...+F(n-1,n-1)个
                //以i为根总共n个节点的BST有 F(i,n)=G(i-1)*G(i+1->n)个
                //BST形态数量之和一共有多少个节点有关 G(i+1->n)=G(n-i)
                //所以G(n)= G(0)*G(n-1)+G(1)*G(n-2)+...
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        return dp[n];
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64611.html

leetcode95-96 Unique Binary Search Trees I-II

摘要：在这里我们使用数组中下标为的位置来记录个元素可以组成的平衡二叉树的数量。在递归的过程中，我们找到以当前节点作为根节点的所有平衡二叉树，并将结果以形式返回上一级调用。题目要求 Given n, how many structurally unique BSTs (binary search trees) that store values 1...n? For example, Gi...

morgan 2019-08-15 11:06 评论0 收藏0
[Leetcode-Dynamic Programming]Unique Binary Search

Unique Binary Search TreesGiven n, how many structurally unique BSTs (binary search trees) that store values 1...n? For example,Given n = 3, there are a total of 5 unique BSTs. 1 3 3 ...

MartinDai 2019-08-16 10:27 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
[Leetcode] Validate Binary Search Tree 验证二叉搜索树

摘要：注意这里的结构和不同的二叉树遍历一样，如果到空节点就返回，否则递归遍历左节点和右节点。唯一不同是加入了和，所以要在递归之前先判断是否符合和的条件。代码如果该节点大于上限返回假如果该节点小于下限返回假递归判断左子树和右子树 Validate Binary Search Tree Given a binary tree, determine if it is a valid binary...

fuchenxuan 2019-08-14 12:40 评论0 收藏0
LeetCode 之 JavaScript 解答第98题 —— 验证二叉搜索树

摘要：小鹿题目验证二叉搜索树给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征节点的左子树只包含小于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。算法思路定义全局的变量，用来返回是否为二叉搜索树。 Time：2019/4/24Title: Vaildata Binary Search TreeDifficulty: MediumAuthor: 小鹿 ...

用户84 2019-08-23 17:12 评论0 收藏0