題目描述

給定一個整數 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題解敬請期待。

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

關鍵字: 個數 右子 二叉