【原】刻意练习：LeetCode实战 -- 不同的二叉搜索树

背景

今天，第二期基础算法（Leetcode）刻意练习训练营 的打卡任务是“不同的二叉搜索树 II”，而LeetCode也有“不同的二叉搜索树”题目，故一起写了。

---

题目

• 题号：96

• 难度：中等

• https:///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


---

实现

第一种：动态规划

令G(n)表示n个节点二叉排序树的个数，f(i)表示以i作为根节点的二叉排序树的个数。

因此有：G(n) = f(1) + f(2) + f(3) + ... + f(n)

以i为根节点的左子树有i-1个节点，因此左子树有G(i-1)种二叉排序树

右子树有n-i个节点，因此右子树有G(n-i)种二叉排序树

从而得到：f(i) = G(i-1)*G(n-i)

最后得到：

G(0) = 1
G(1) = 1
G(2) = G(0)*G(1) + G(1)*G(0)
G(3) = G(0)*G(2) + G(1)*G(1) + G(2)*G(0)
......
G(n) = G(0)*G(n-1) + G(1)*G(n-2) + G(2)G(n-3) + ... + G(n-1)*G(0)


• 执行结果：通过

• 执行用时：48 ms, 在所有 C# 提交中击败了 66.10% 的用户

• 内存消耗：14.6 MB, 在所有 C# 提交中击败了 16.67% 的用户

public class Solution
{
    public int NumTrees(int n)
    {
        if (n == 0 || n == 1)
            return 1;

        int[] dp = new int[n + 1];
        dp[0] = 1;
        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];
    }
}


---