备案控制台

开发者社区人工智能文章正文

Leetcode-Medium 96.Unique Binary Search Trees

2022-05-20 97

版权

版权声明：

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Leetcode-Medium 96.Unique Binary Search Trees

题目描述

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

思路

动态规划

假设n个节点存在

令G(n)的从1到n可以形成二叉排序树个数

令f(i)为以i为根的二叉搜索树的个数

即有:G(n) = f(1) + f(2) + f(3) + f(4) + ... + f(n)

n为根节点，当i为根节点时，其左子树节点个数为[1,2,3,...,i-1]，右子树节点个数为[i+1,i+2,...n]，所以当i为根节点时，其左子树节点个数为i-1个，右子树节点为n-i，即f(i) = G(i-1)*G(n-i),

上面两式可得:G(n) = G(0)G(n-1)+G(1)(n-2)+...+G(n-1)*G(0)

https://leetcode-cn.com/problems/unique-binary-search-trees/solution/dong-tai-gui-hua-by-powcai-4/

代码实现

class Solution:
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        G = [0]*(n+1)
        G[0], G[1] = 1, 1
        for i in range(2, n+1):
            for j in range(1, i+1):
                G[i] += G[j-1] * G[i-j]
        return G[n]

文章标签：

机器学习/深度学习

关键词：

LeetCode search

LeetCode trees

LeetCode unique binary trees

LeetCode binary trees

致Great_VIP

目录

相关文章

xindoo

Leetcode 74. Search a 2D Matrix

这道题很简单，为此专门写篇博客其实算博客凑数了。给你一个每一行每一列都是增序，且每一行第一个数都大于上一行末尾数的矩阵，让你判断某个数在这个矩阵中是否存在。假设矩阵是m*n，扫一遍的时间复杂度就是O(m*n)，题目中给出的这么特殊的矩阵，时间复杂度可以降到O(m+n)，具体代码如下，写的比较挫。

xindoo

85 1 1

xindoo

Leetcode Minimum Depth of Binary Tree （面试题推荐）

计算树的最小深度很简单的一道题，只需要遍历一次树，到叶子节点的时候计算一下深度和当前最小深度比较，保存最小值就行。我在这用了一个全局变量 mindepth。总感觉我这代码写的不够简练，求更精简的方法。

xindoo

47 0 0

xindoo

Leetcode Binary Tree Postorder Traversal(面试题推荐)

非递后续归遍历二叉树，肯定得用到栈。先序遍历很好写，但后续遍历就不是那么容易了。只需要设置个指针pre，指向最后输出的那个节点就行了，只要判断cur指针指向的是上次输出节点的父节点，且cur无其他未遍历的节点，这个时候就把cur节点输出即可，然后更改pre。原理是要遍历当前节点，其所有子节点都必须遍历完，因为肯定是先左后右，所以只需一个指针保持前一次输出的结果即可。

xindoo

51 0 0

xindoo

Leetcode 236. Lowest Common Ancestor of a Binary Tree

根据LCA的定义，二叉树中最小公共祖先就是两个节点p和q最近的共同祖先节点，LCA的定义没什么好解释的，主要是这道题的解法。

xindoo

38 0 0

程序媛三妹ya

|

算法

LeetCode contest 190 5418. 二叉树中的伪回文路径 Pseudo-Palindromic Paths in a Binary Tree

LeetCode contest 190 5418. 二叉树中的伪回文路径 Pseudo-Palindromic Paths in a Binary Tree

程序媛三妹ya

105 0 0

程序媛三妹ya

LeetCode Contest 178-1367. 二叉树中的列表 Linked List in Binary Tree

LeetCode Contest 178-1367. 二叉树中的列表 Linked List in Binary Tree

程序媛三妹ya

85 0 0

ruicore

|

Python

LeetCode 401. Binary Watch

二进制手表顶部有 4 个 LED 代表小时（0-11），底部的 6 个 LED 代表分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。

ruicore

107 0 0

LeetCode 401. Binary Watch

程序媛三妹ya

|

算法 Python

LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree

LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree

程序媛三妹ya

128 0 0

程序媛三妹ya

LeetCode 102. 二叉树的层序遍历 Binary Tree Level Order Traversal

LeetCode 102. 二叉树的层序遍历 Binary Tree Level Order Traversal

程序媛三妹ya

92 0 0

程序媛三妹ya

LeetCode 104. 二叉树的最大深度 Maximum Depth of Binary Tree

LeetCode 104. 二叉树的最大深度 Maximum Depth of Binary Tree

程序媛三妹ya

99 0 0

热门文章

最新文章

# Leetcode 14：Longest Common Prefix 最长公共前缀

LeetCode 191 Number of 1 Bits（1 比特的数字们）

LeetCode:Spiral Matrix I II

LeetCode 82 Remove Duplicates from Sorted List II（从已排序链表中移除重复元素）（Linked List）（*）

【LeetCode从零单排】No129 Sum Root to Leaf Numbers

LeetCode 21：合并两个有序链表 Merge Two Sorted Lists

[LeetCode] Rotate List 旋转链表

LeetCode:Valid Parentheses

[LeetCode] Number of Islands II

LeetCode.每日一题 1039. 多边形三角剖分的最低得分

力扣合并两个有序数列||移除元素

LeetCode hard也就这么回事

LeetCode链表hard 有思路？但写不出来？

滑动窗口最大值（leetcode hot100）

LeetCode438题（无敌双指针——滑动窗口）

接雨水（leetcode hot100）

每日一题：力扣328. 奇偶链表

【LeetCode力扣】单调栈解决Next Greater Number（下一个更大值）问题

【LeetCode力扣】面试题 17.14. 最小K个数（top-k问题）

leetcode代码记录（旋转图像

相关电子书

更多

Building a Search Engine

Semantic Search--Fast Results from Large,Foreign Language Corpora

Large Data Files, Object Stores,and Deep Learning—Lessons Learned While Looking for Extra-Terrestrial Life

下一篇

阿里云OSS设置跨域访问