C++不同的二叉搜索樹問題怎么解決

本文小編為大家詳細介紹“C++不同的二叉搜索樹問題怎么解決”，內容詳細，步驟清晰，細節處理妥當，希望這篇“C++不同的二叉搜索樹問題怎么解決”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。

原題

給定一個整數 n，求以 1 ... n 為節點組成的二叉搜索樹有多少種？

示例:

輸入: 3
輸出: 5
解釋:
給定 n = 3, 一共有 5 種不同結構的二叉搜索樹:

   1         3     3      2     1
    \        /     /      / \      \
    3      2     1     1   3      2
    /      /       \                    \
   2     1         2                    3

解題

這道題看到的第一眼，就和之前的格雷編碼一樣，又想用動態規劃，每次都是遍歷所有情況去檢查是否有效，但感覺時間復雜度會很高，找找看有沒有什么更高效的做法。

所謂高效，也就是尋找規律了，最好的是可以遞推，下一次運算可以利用之前的結果，而本題就是用這種規律的。我們來試試 n 等于0、1、2、3的情況：

n = 0，只有1種。

n = 1，也只有1種。

n = 2，有2種
1           2
 \         /
   2    1

n = 3，有5種
   1         3     3      2     1
    \        /     /      / \      \
    3      2     1     1   3      2
    /      /       \                    \
   2     1         2                    3

讓我們回想一下什么叫二叉搜索樹，就是針對每個節點，其左子樹中所有節點都比它小，其右子樹中所有節點都比它大。

再想一下，如果我們針對根選中的情況下，左右子樹節點的個數其實也已經定下來了，那么假設同樣是 3 個節點，"1、2、3"和"4、5、6"可以組成二叉搜索樹，從數量上講是一樣的，因為大小關系沒有變。

因此，我們可以說，針對二叉搜索樹，其不用考慮值具體是多少，只需要考慮其大小關系即可，那么這就符合上面我所希望的場景了，下一次的運算可以利用之前的結果。

以這道題來說，其具體規律就是：

1. 從 1 開始遍歷直至 n，以每個節點作為根節點，這樣就能計算出左右各個子樹的所有節點數。

2. 當我們知道了個數，也就可以利用之前計算的結果，獲得左右子樹可能的情況，兩者相乘，也就是在當前根的情況，所有二叉搜索樹的情況。

3. 將所有根節點的總計算出的數量做累加，也就得出了當前節點數的總情況。

讓我們看看代碼：

class Solution {
    public int numTrees(int n) {
            // 存放中間結果
        int[] result = new int[n + 1];
        result[0] = 1;
        result[1] = 1;

        for (int i = 2; i <= n; i++) {
            int count = 0;
            for (int j = 1; j <= i; j++) {
                // 左子樹總節點數 + 右子樹總節點數
                count += (result[j - 1] * result[i - j]);
            }
            result[i] = count;
        }

        return result[n];
    }
}

提交OK， 執行用時：0 ms，內存消耗：33.2 MB。

讀到這里，這篇“C++不同的二叉搜索樹問題怎么解決”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。