0096. Unique Binary Search Trees (Medium)

Question

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Example:

1
2
3
4

Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:

1
2
3
4
5

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

分析/解題

還記得什麼是二元搜尋樹嗎？
不知道的話，可以翻閱前面的第16篇的介紹歐！
簡言之，一個合法的BST除了左邊的節點要全小於根節點，右邊的節點要全大於根節點 外，
其左右子樹也要是BST 才行。
觀察n=3的狀況，我們可以將其歸納成3類：
以1為根節點/以2為根節點/以3為根節點。

首先是1為根節點的狀況：
左邊沒有比其小的節點，故只有一種可能；
右邊有2跟3的組合，相當於n=2的時候的狀況(2種)。
(2跟3等價於1跟2兩個節點會有的組合)

再來是2為根節點的狀況：
左邊只有1種可能(1這個節點)；
右邊也只有1種可能(3這個節點)。

最後是3為根節點的狀況：
左邊是1跟2的組合(2種)，
右邊只有1種可能。

如果我們將n的組合命名為函式f(n)，
那麼顯然f(0)=1(只有一種可能)，f(1)=1。

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

掌握這個規律的狀態，我們可以得到f(n)的計算方式：
f(0)*f(n-1) + f(1)*f(n-2) + … + f(n-1)*f(0)
那麼，從f(1)開始起算的話，
我們可以一路疊加將f(1)到f(n-1)都算出來，
最後得到我們要的f(n)。
讓f(n)能夠化成f(n-1)或較小的項次的組合，一路化簡到能直接確認的值，
所以這個就是典型的動態規劃的範例。

Java

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(n²), O(n)
由於計算時兩層迴圈最大都要經歷n，故時間上會和n的平方相關)

「可以改成遞迴 的方式嗎？」
(可以，我們只要將dp改成字典或HashMap，開一個函式search，
令其在找不到值的時候呼叫自己如 sum += search(i-1) * search(n-i)，
最後也會如同迴圈的解法一樣一路拆解到最底下，
讀者可以自行嘗試看看，實測上兩者速度在實作正確的狀況下，
應該是感受不出太明顯的差異的。)

Special Thanks suggestions/corrections from viewers:
From Python Taiwan
 曾淯銘: 更正BST的筆誤(連結是對的，本文打錯，是左<根<右，已更正)
 ChenRay Hsieh: 本文的解其實等同於Catalan number，讀者可參考閱讀。

從LeetCode學演算法，我們下次見囉，掰~