Leetcode 96. 不同的二叉搜索树_leetcode 96解析

1、问题分析

题目链接：https://leetcode-cn.com/problems/unique-binary-search-trees/
  可以使用动态规划求解，总体思路就是固定根节点，然后求左右子节点各有多少种情况，将结果相乘，这里注意单位个数为 1。代码我已经进行了详细的注释，理解应该没有问题，读者可以作为参考，如果看不懂(可以多看几遍)，欢迎留言哦！我看到会解答一下。

状态转移方程如下：

d p [ n ] = { 2 × d p [ 0 ] × d p [ n − 0 − 1 ] + 2 × d p [ 1 ] × d p [ n − 1 − 1 ] + 2 × d p [ 2 ] × d p [ n − 2 − 1 ] + . . . + d p [ n 2 ] × d p [ n 2 ] , ( n % 2 = = 1 , i . e . n   i s   o d d ) 2 × d p [ 0 ] × d p [ n − 0 − 1 ] + 2 × d p [ 1 ] × d p [ n − 1 − 1 ] + 2 × d p [ 2 ] × d p [ n − 2 − 1 ] + . . . + d p [ n 2 − 1 ] × d p [ n 2 − 1 ] , ( n % 2 = = 0 , i . e . n   i s   e v e n ) dp[n] = \left\{

$$\begin{array}{l} 2 \times dp[0] \times dp[n - 0 - 1]{\rm{ + }}2 \times dp[1] \times dp[n - 1 - 1] + 2 \times dp[2] \times dp[n - 2 - 1] + ... + dp[\frac{n}{2}] \times dp[\frac{n}{2}],(n\% 2 = = 1,{\rm{i}}{\rm{.e}}{\rm{. n \,is \,odd}})\\ 2 \times dp[0] \times dp[n - 0 - 1]{\rm{ + }}2 \times dp[1] \times dp[n - 1 - 1] + 2 \times dp[2] \times dp[n - 2 - 1] + ... + dp[\frac{n}{2} - 1] \times dp[\frac{n}{2} - 1],(n\% 2 = = 0,{\rm{i}}{\rm{.e}}{\rm{. n\, is\, even}}) \end{array}$$ \right. dp[n]={2×dp[0]×dp[n−0−1]+2×dp[1]×dp[n−1−1]+2×dp[2]×dp[n−2−1]+...+dp[2n​]×dp[2n​],(n%2==1,i.e.nisodd)2×dp[0]×dp[n−0−1]+2×dp[1]×dp[n−1−1]+2×dp[2]×dp[n−2−1]+...+dp[2n​−1]×dp[2n​−1],(n%2==0,i.e.niseven)​

2、问题解决

  笔者以C++方式解决。

#include "iostream"

using namespace std;

#include "algorithm"
#include "vector"
#include "queue"
#include "set"
#include "map"
#include "cstring"
#include "stack"

class Solution {
private:
    // 定义 dp 数组 保存不同 n 为节点组成的二叉搜索树的个数
    // 例如 dp[2] 代表 有1,2 即 2个节点组成的二叉搜索树的个数
    vector<int> dp;
public:
    int numTrees(int n) {
        // 初始化  dp 数组
        dp.resize(n + 1);
        // 这里需要注意的是 不能直接使用 numTrees(n) 进行递归，因为这里涉及到初始化的操作
        // 否则的话，每一次递归，dp 数组大小就会变化
        return deal(n);
    }

    /**
     * 计算  n 为节点组成的二叉搜索树的个数
     * 动态规划状态转移方程为：dp[n] = 2 x dp[0] x dp[n-1] + 2 x dp[1] x dp[n-2] + 2 x dp[2] x dp[n-3] + ... + dp[n/2] x dp[n/2]
     * 总体思路就是固定根节点，然后求左右子节点各有多少种情况，将结果相乘，这里注意单位个数为 1
     * @param n 节点个数
     * @return
     */
    int deal(int n) {
        // 如果节点已经计算过，直接返回
        if (dp[n] != 0) {
            return dp[n];
        }

        // 对应超出边界的直接取单位值即可
        if (n <= 0) {
            dp[0] = 1;
            return 1;
        }

        // 递归边界
        if (n == 1) {
            dp[n] = 1;
            return dp[n];
        }
        else if (n == 2) {
            dp[n] = 2;
            return dp[n];
        }

        // 根据博客上面的详细公式可以写出如下程序
        // 分为奇数和偶数两种情况
        if (n % 2 == 1) {
            for (int i = 0; i <= n / 2; ++i) {
                if (i != n / 2) {
                    // 因为左右两边的对称性，所以需要乘 2
                    dp[n] += 2 * deal(i) * deal(n - i - 1);
                }
                else {
                    // 中间节点 本身就是对称的，只有一种情况
                    dp[n] += deal(i) * deal(n - i - 1);
                }
            }
        }
        else if (n % 2 == 0) {
            for (int i = 0; i < n / 2; ++i) {
                dp[n] += 2 * deal(i) * deal(n - i - 1);
            }
        }

        return dp[n];

    }

};

int main() {
    int n = 3;
    Solution *pSolution = new Solution;
    int i = pSolution->numTrees(n);
    cout << i << endl;
    system("pause");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

运行结果

有点菜，有时间再优化一下。

3、总结

  书上的代码直接运行绝大部分是对的，但是总有一些软件的更新使得作者无能为力。之前的API是对的，但是之后就废弃了或修改了是常有的事。所以我们需要跟踪源代码。这只是一个小小的问题，如果没有前辈的无私奉献，很难想象我们自己一天能学到多少内容。感谢各位前辈的辛勤付出，让我们少走了很多的弯路！

点个赞再走呗！欢迎留言哦！