Leetcode 96. Unique Binary Search Trees

給定一個數字n，n 個節點可以組成多少二元樹?

Python

Binary Search Tree的規則:左邊的節點要全小於根節點，右邊的節點要全大於根節點

方法一 : 動態規劃

dp[i]等於左子樹有0個節點，左子樹有1個節點，左子樹有2個節點….，而右子樹則為dp[i – j – 1]，最後左子樹節點*右子樹節點就是有可能的解加總

ex : 計算n=3的組合算法為：
f(0) * f(2) + f(1) * f(1) + f(2) * f(0)

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = 1
        
        for i in range(1, n + 1):
            for j in range(0, i):
                dp[i] += dp[j] * dp[i - j - 1]
            
        return dp[n]

方法二 : 遞歸

比i小的數1...i-1作為左子樹，比i大的數i+1...n作為右子樹，左子樹的排列和右子樹的排列的乘積則為答案

class Solution:
    def numTrees(self, n: int) -> int:
        if n <= 1:
            return 1
        sum = 0
        for i in range(1, n + 1):
            sum += self.numTrees(i - 1) * self.numTrees(n - i)
        return sum

C++

方法一 : 動態規劃

用dp[i]表示由i個節點構成的不同的二叉搜索樹的數量。因為二叉搜索樹是有序的，所以我們可以通過在每個位置上插入不同的節點來構造不同的二叉搜索樹。假設我們選擇第j個節點作為根節點，那麼左子樹就有j-1個節點，右子樹就有i-j個節點。那麼由i個節點構成的不同的二叉搜索樹的數量就是左子樹的數量乘以右子樹的數量。

時間複雜度為O(n)，空間複雜度為O(1)。

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 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];
    }
};

方法二 : 遞歸

假設我們要構造由1到n這n個節點組成的二叉搜索樹，那麼我們可以枚舉根節點的位置，將1到n分為兩個部分，左邊的部分由1到j-1構成，右邊的部分由j+1到n構成。那麼左右兩邊就可以遞歸地構造出子樹，最終的方案數就是左右子樹的方案數的乘積。對於每一個位置j，都有numTrees(j-1) * numTrees(n-j)種不同的方案。將它們累加起來就是答案。

時間複雜度為O(n^2)，空間複雜度為O(n)。

class Solution {
public:
    int numTrees(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        int res = 0;
        for (int i = 1; i <= n; ++i) {
            res += numTrees(i - 1) * numTrees(n - i);
        }
        return res;
    }
};

Python

C++

相關