专栏首页木又AI帮打卡群2刷题总结1013——不同的二叉搜索树

打卡群2刷题总结1013——不同的二叉搜索树


leetcode第96题:不同的二叉搜索树

https://leetcode-cn.com/problems/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个节点的树,除了根节点外,节点在左子树和右子树上的数目分布可能是左0右n-1,左1右n-2,...,左n-2右1,左n-1右0。

用公式表示:dp[n] = dp[0] * dp[n - 1] + dp[1] * dp[n - 2] + ··· + dp[n - 2] * dp[1] + dp[n - 1] * dp[0]

【代码】

python版本

class Solution:
    def numTrees(self, n: int) -> int:
        if n < 2:
            return n
        
        dp = [0] * (n + 1)
        dp[0], dp[1] = 1, 1
        # dp[i] = dp[0] * dp[i - 1] + dp[1] * dp[i - 2] + ... + dp[i - 1] * dp[0]
        for i in range(2, n + 1):
            for j in range(i):
                dp[i] += dp[j] * dp[i - j - 1]
        print(dp)
        return dp[-1]

【相似题目】

95. 不同的二叉搜索树 II

解题思路:dfs递归遍历。

98. 验证二叉搜索树

解题思路:递归遍历二叉树,并记录当前节点允许的最大值和最小值,判断当前节点的值是否在允许范围内。

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-10-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 打卡群刷题总结0805——不同的二叉搜索树

    PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。

    木又AI帮
  • 打卡群刷题总结0807——验证二叉搜索树

    PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。

    木又AI帮
  • 打卡群2刷题总结1010——二叉树的层序遍历

    https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

    木又AI帮
  • 打卡群2刷题总结1012——二叉树的最大深度

    https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

    木又AI帮
  • 打卡群2刷题总结1009——二叉树的中序遍历

    https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

    木又AI帮
  • 打卡群刷题总结0721——搜索二维矩阵

    链接:https://leetcode-cn.com/problems/search-a-2d-matrix

    木又AI帮
  • 【leetcode刷题】20T49-不同的二叉搜索树

    https://leetcode-cn.com/problems/unique-binary-search-trees

    木又AI帮
  • 打卡群刷题总结0804——二叉树的中序遍历

    非递归解法,需要使用栈结构,同时使用一个visit数组标识该节点是否访问过其孩子节点。得到visit栈顶元素,判断是否访问过;如果访问过,则val加入到结果中;...

    木又AI帮
  • 打卡群刷题总结0808——二叉树的层序遍历

    PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。

    木又AI帮
  • 打卡群2刷题总结1002——搜索插入位置

    https://leetcode-cn.com/problems/search-insert-position/

    木又AI帮
  • 打卡群刷题总结0814——二叉树展开为链表

    链接:https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node

    木又AI帮
  • 打卡群刷题总结0813——二叉树展开为链表

    链接:https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list

    木又AI帮
  • ​LeetCode刷题实战96:不同的二叉搜索树

    https://leetcode-cn.com/problems/unique-binary-search-trees/

    程序IT圈
  • 打卡群2刷题总结1003——搜索旋转排序数组

    https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

    木又AI帮
  • ​LeetCode刷题实战95:不同的二叉搜索树 II

    https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

    程序IT圈
  • 打卡群刷题总结0809——二叉树的锯齿形层次遍历

    链接:https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal

    木又AI帮
  • 杭电OJ刷题指南

    说起来刷题,很多大牛都会推荐LeetCode或者牛客网,这两个网站是刷题的好网站。但对新手来说,有一点难度,新手建议先去杭电OJ刷题,这里的题目难度不大,如果你...

    Jasonangel
  • 打卡群2刷题总结1011——从前序与中序遍历序列构造二叉树

    https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder...

    木又AI帮
  • 本周小结!(二叉树)

    发现大家周末的时候貌似都不在学习状态,周末的文章浏览量和打卡情况照工作日差很多呀,可能是本周日是工作日了,周六得好好放松放松,哈哈,理解理解,但我还不能不更啊,...

    代码随想录

扫码关注云+社区

领取腾讯云代金券