leetcode-96 不同的二叉搜索树

题目描述：给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

• 1 <= n <= 19

代码实现

递归实现

class Solution {
    public int numTrees(int n) {
        return numTrees(1, n);
    }

    public int numTrees(int start, int end) {
        if (end <= start) {
            return 1;
        }
        int sum = 0;
        for (int idx = start; idx <= end; idx++) {
            int leftTreeStart = start;
            int leftTreeEnd = idx - 1;
            int rightTreeStart = idx + 1;
            int rightTreeEnd = end;
            int leftNum = (leftTreeEnd - leftTreeStart < 1) ? 1 : numTrees(leftTreeStart, leftTreeEnd);
            int rightNum = (rightTreeEnd - rightTreeStart < 1) ? 1 : numTrees(rightTreeStart, rightTreeEnd);
            sum += leftNum * rightNum;
        }
        return sum;
    }
}