题目描述

给定一个整数 n, 求以1 ... n为节点组成的二叉搜索树有多少种? 示例：

输入: 3

输出: 5

解释:

给定n = 3,一共有5种不同结构的二叉搜索树，如下图所示：

解题思路

首先要清楚什么是二叉搜索树, 如果一棵树是二叉搜索树, 那么左子树的所有节点的值小于根节点的值, 右子树的所有节点大于根节点的值. 对于题目描述的问题:

当n = 1时, 有1种情况;

当n = 2时, 有2种情况;

当n = 3时, 有5种情况;

...

...

想找到关于n的通项公式吗? 先看一下怎么构造递推关系吧. 设a(n)表示能组成的二叉搜索树的个数, 那么:

a(0) = 1(取a(0)方便计算);

a(1) = 1;

a(2) = 2;

a(3) = 5;

当n = 4时, 结果中按照根节点的不同可以分为根节点时1, 2, 3, 4四种情况. 以根节点取2为例, 其左子树只能包含1, 右子树只能包含3, 4. 并且左子树的个数为a(1), 右子树的个数为a(2), 根据乘法原理, 根节点取2时共有a(1)xa(2)种结果, 所以:

<code>a(4)=a(0)a(3)+a(1)a(2)+a(2)a(1)+a(3)a(0)/<code> 

对于任意一个大于1的整数n:

<code>a(n)=a(0)a(n-1)+a(1)a(n-2)+...+a(n-2)a(1)+a(n-1)a(0)/<code>

根据以上递推公式即可计算出n取任意值时的结果.

代码实现

<code>class Solution:
    def numTrees(self, n: int) -> int:
        # 保存递推初始值
        res = [1, 1, 2, 5]
        if n <= 3:
            return res[n]
        else:
            for i in range(4, n+1):
                s = 0
                for j in range(0, i):
                    s += (res[j] * res[i-1-j])
                res.append(s)
        return res[-1]/<code>

更多leetcode题解敬请期待。

閱讀更多 深度學習工程師 的文章

關鍵字: 个数 右子 二叉