🌗 96. 不同的二叉搜索树

难度: 🌗

• 问题描述
• 解法
• 输出

问题描述

---

解法

class Solution {
    public int numTrees(int n) {
        // 思路：
        // 1 - n 每个节点均可以成为根节点
        // 从而将二叉搜索数分为了左右两半
        // 根据二叉搜索数节点个数，进行递归
        // f(0) = 0
        // f(1) = 1
        // f(2) = (0, 1) + (1, 0) = 2
        // f(3) = (0, 2) + (1, 1) + (2, 0) = 5
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i ++) {
            if(i % 2 == 0) {
                for(int k = 0; k < i / 2; k ++) {
                    dp[i] += dp[k] * dp[i - 1 - k];
                }
                dp[i] *= 2;
            } else {
                for(int k = 0; k < (i - 1) / 2; k ++) {
                    dp[i] += dp[k] * dp[i - 1 - k];
                }
                dp[i] *= 2;
                dp[i] += dp[(i - 1) / 2] * dp[(i - 1) / 2] ;
            }
        }
        return dp[n];
    }
}

---

输出