不同的二叉搜索树

• 96. 不同的二叉搜索树

  难度：中等

  给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

  示例:

  输入: 3
  输出: 5
  解释:
  给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
  
     1         3     3      2      1
      \       /     /      / \      \
       3     2     1      1   3      2
      /     /       \                 \
     2     1         2                 3

  自底向上的动态规划

给定序列 1⋯，n1，⋯n，我们选择数字 i 作为根，则根为 i 的所有二叉搜索树的集合是左子树集合和右子树集合的笛卡尔积

举例而言，创建以 3 为根、长度为 7 的不同二叉搜索树，整个序列是 [1, 2, 3, 4, 5, 6, 7]，我们需要从左子序列 [1, 2] 构建左子树，从右子序列 [4, 5, 6, 7] 构建右子树，然后将它们组合（即笛卡尔积）。

class Solution {
    public int numTrees(int n) {
        int dp[] = new int[n + 1];
        dp[0] = 1;//有零个节点时，二叉树只有一种结构
        dp[1] = 1;//有一个节点时，二叉树只有一种结构

        //有多个节点时，选择一个节点作为根节点，二叉树的结构的数目是：
        //左子树的节点的结构数目乘以右子树的节点的结构数目
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}

参考文献

官方题解

赏

谢谢你请我吃糖果

微信