Leetcode 96. 不同的二叉搜索树

比眉伴天荒 2023-02-11 07:10 27阅读 0赞

### Leetcode 96. 不同的二叉搜索树 ###

*  1、问题分析
 *  2、问题解决
 *  3、总结

# 1、问题分析 #

题目链接：[https://leetcode-cn.com/problems/unique-binary-search-trees/][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;
    }

运行结果

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70]

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

# 3、总结 #

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

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

[https_leetcode-cn.com_problems_unique-binary-search-trees]: https://leetcode-cn.com/problems/unique-binary-search-trees/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200522084102304.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3,size_16,color_FFFFFF,t_70