C++实现LeetCode(96.独一无二的二叉搜索树)

[LeetCode] 96. Unique Binary Search Trees 独一无二的二叉搜索树

Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?

Example:

Input: 3
Output: 5
Explanation:
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

这道题实际上是 卡塔兰数 Catalan Numbe 的一个例子，如果对卡塔兰数不熟悉的童鞋可能真不太好做。话说其实我也是今天才知道的好嘛 -.-|||，为啥我以前都不知道捏？！为啥卡塔兰数不像斐波那契数那样人尽皆知呢，是我太孤陋寡闻么？！不过今天知道也不晚，不断的学习新的东西，这才是刷题的意义所在嘛! 好了，废话不多说了，赶紧回到题目上来吧。我们先来看当 n = 1 的情况，只能形成唯一的一棵二叉搜索树，n分别为 1,2,3 的情况如下所示：

                    1                        n = 1

                2        1                   n = 2
/          \
1            2

1         3     3      2      1           n = 3
\       /     /      / \      \
3     2     1      1   3      2
/     /       \                 \
2     1         2                 3

就跟斐波那契数列一样，我们把 n = 0 时赋为1，因为空树也算一种二叉搜索树，那么 n = 1 时的情况可以看做是其左子树个数乘以右子树的个数，左右子树都是空树，所以1乘1还是1。那么 n = 2 时，由于1和2都可以为根，分别算出来，再把它们加起来即可。n = 2 的情况可由下面式子算出（这里的 dp[i] 表示当有i个数字能组成的 BST 的个数）：

dp[2] =  dp[0] * dp[1]　　　(1为根的情况，则左子树一定不存在，右子树可以有一个数字)

　　　　+ dp[1] * dp[0]　　  (2为根的情况，则左子树可以有一个数字，右子树一定不存在)

同理可写出 n = 3 的计算方法：

dp[3] =  dp[0] * dp[2]　　　(1为根的情况，则左子树一定不存在，右子树可以有两个数字)

　　　　+ dp[1] * dp[1]　　  (2为根的情况，则左右子树都可以各有一个数字)

 　　　  + dp[2] * dp[0]　　  (3为根的情况，则左子树可以有两个数字，右子树一定不存在)

我们根据以上的分析，可以写出代码如下：

解法一：

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1);
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        return dp[n];
    }
};

由卡特兰数的递推式还可以推导出其通项公式，即 C(2n,n)/(n+1)，表示在 2n 个数字中任取n个数的方法再除以 n+1，只要你还没有忘记高中的排列组合的知识，就不难写出下面的代码，注意在相乘的时候为了防止整型数溢出，要将结果 res 定义为长整型，参见代码如下：

解法二：

class Solution {
public:
    int numTrees(int n) {
        long res = 1;
        for (int i = n + 1; i <= 2 * n; ++i) {
            res = res * i / (i - n);
        }
        return res / (n + 1);
    }
};

到此这篇关于C++实现LeetCode(96.独一无二的二叉搜索树)的文章就介绍到这了,更多相关C++实现独一无二的二叉搜索树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(187.求重复的DNA序列)

    [LeetCode] 187. Repeated DNA Sequences 求重复的DNA序列 All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA. Wr

  • C++实现LeetCode(89.格雷码)

    C++实现LeetCode(89.格雷码)

    [LeetCode] 89.Gray Code 格雷码 The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code se

  • C++实现LeetCode(87.搅乱字符串)

    [LeetCode] 87. Scramble String 搅乱字符串 Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively. Below is one possible representation of s1 = "great":     great /    \ gr    eat / \    /  \

  • C++实现LeetCode(137.单独的数字之二)

    [LeetCode] 137. Single Number II 单独的数字之二 Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you

  • C++实现LeetCode(93.复原IP地址)

    [LeetCode] 93.Restore IP Addresses 复原IP地址 Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example: Input: "25525511135" Output: ["255.255.11.135", "255.255.111.35"] 这

  • C++实现LeetCode(136.单独的数字)

    [LeetCode] 136.Single Number 单独的数字 Given a non-empty array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

  • C++实现LeetCode(95.独一无二的二叉搜索树之二)

    [LeetCode] 95. Unique Binary Search Trees II 独一无二的二叉搜索树之二 Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n. Example: Input: 3 Output: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3],

  • C++实现LeetCode(91.解码方法)

    [LeetCode] 91. Decode Ways 解码方法 A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given a non-empty string containing only digits, determine the total number of ways to

  • C++实现LeetCode(96.独一无二的二叉搜索树)

    [LeetCode] 96. Unique Binary Search Trees 独一无二的二叉搜索树 Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n? Example: Input: 3 Output: 5 Explanation: Given n = 3, there are a total of 5 unique BST's: 1         3  

  • C++实现LeetCode(99.复原二叉搜索树)

    [LeetCode] 99. Recover Binary Search Tree 复原二叉搜索树 Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Example 1: Input: [1,3,null,null,2]    1 / 3 \ 2 Output: [3,1,null,null,2]    3 / 1

  • C++实现LeetCode(98.验证二叉搜索树)

    [LeetCode] 98. Validate Binary Search Tree 验证二叉搜索树 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The ri

  • C++实现LeetCode(109.将有序链表转为二叉搜索树)

    [LeetCode] 109.Convert Sorted List to Binary Search Tree 将有序链表转为二叉搜索树 Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary

  • C++实现LeetCode(108.将有序数组转为二叉搜索树)

    [LeetCode] 108.Convert Sorted Array to Binary Search Tree 将有序数组转为二叉搜索树 Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in wh

  • C++实现LeetCode(173.二叉搜索树迭代器)

    [LeetCode] 173.Binary Search Tree Iterator 二叉搜索树迭代器 Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST. Calling next() will return the next smallest number in the BST. Note: next() and

  • Java数据结构之二叉搜索树详解

    Java数据结构之二叉搜索树详解

    目录 前言 性质 实现 节点结构 初始化 插入节点 查找节点 删除节点 最后 前言 今天leetcode的每日一题450是关于删除二叉搜索树节点的,题目要求删除指定值的节点,并且需要保证二叉搜索树性质不变,做完之后,我觉得这道题将二叉搜索树特性凸显的很好,首先需要查找指定节点,然后删除节点并且保持二叉搜索树性质不变,就想利用这个题目讲讲二叉搜索树. 二叉搜索树作为一个经典的数据结构,具有链表的快速插入与删除的特点,同时查询效率也很优秀,所以应用十分广泛,例如在文件系统和数据库系统一般会采用这种数

  • Java动态规划方式解决不同的二叉搜索树

    Java动态规划方式解决不同的二叉搜索树

    目录 一.题目描述 二.思路 三.代码 一.题目描述 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数. 来源:https://leetcode.cn/problems/unique-binary-search-trees/ 二.思路 本题可以使用动态规划的方式解决,我们先来看一下大题思路.以 n = 3 为例,n = 3 时的不同的二叉搜索树数目,可以通过分别 以 1 为根节点,以 2 为根节点,以 3 为根节点

  • Javascript实现从小到大的数组转换成二叉搜索树

    废话不多说了,直接给大家贴代码了,具体代码如下所示: var Array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; var Tree = createTree(Array); console.log(Tree); // 构造一个节点 function Node(nodeData, leftData, rightData) { this.nodeData = nodeData; this.leftData = leftData; this.rightData = rig

随机推荐