C++不同的二叉搜索树问题怎么解决

本文小编为大家详细介绍“C++不同的二叉搜索树问题怎么解决”，内容详细，步骤清晰，细节处理妥当，希望这篇“C++不同的二叉搜索树问题怎么解决”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。

原题

给定一个整数 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、1、2、3的情况：

n = 0，只有1种。

n = 1，也只有1种。

n = 2，有2种
1           2
 \         /
   2    1

n = 3，有5种
   1         3     3      2     1
    \        /     /      / \      \
    3      2     1     1   3      2
    /      /       \                    \
   2     1         2                    3

让我们回想一下什么叫二叉搜索树，就是针对每个节点，其左子树中所有节点都比它小，其右子树中所有节点都比它大。

再想一下，如果我们针对根选中的情况下，左右子树节点的个数其实也已经定下来了，那么假设同样是 3 个节点，"1、2、3"和"4、5、6"可以组成二叉搜索树，从数量上讲是一样的，因为大小关系没有变。

因此，我们可以说，针对二叉搜索树，其不用考虑值具体是多少，只需要考虑其大小关系即可，那么这就符合上面我所希望的场景了，下一次的运算可以利用之前的结果。

以这道题来说，其具体规律就是：

1. 从 1 开始遍历直至 n，以每个节点作为根节点，这样就能计算出左右各个子树的所有节点数。

2. 当我们知道了个数，也就可以利用之前计算的结果，获得左右子树可能的情况，两者相乘，也就是在当前根的情况，所有二叉搜索树的情况。

3. 将所有根节点的总计算出的数量做累加，也就得出了当前节点数的总情况。

让我们看看代码：

class Solution {
    public int numTrees(int n) {
            // 存放中间结果
        int[] result = new int[n + 1];
        result[0] = 1;
        result[1] = 1;

        for (int i = 2; i <= n; i++) {
            int count = 0;
            for (int j = 1; j <= i; j++) {
                // 左子树总节点数 + 右子树总节点数
                count += (result[j - 1] * result[i - j]);
            }
            result[i] = count;
        }

        return result[n];
    }
}

提交OK， 执行用时：0 ms，内存消耗：33.2 MB。

读到这里，这篇“C++不同的二叉搜索树问题怎么解决”文章已经介绍完毕，想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会，如果想了解更多相关内容的文章，欢迎关注亿速云行业资讯频道。