# 95 - Unique Binary Search Trees II
解法一 - Recursion
如果不知道怎麼用 DP 解,那就回歸到最基本的東西 - 用暴力解。
我們可以先假設 recursive function 要回傳的東西是 1 到 n 的所有可能樹,那 recursive function 的參數就應該包含 start 跟 end。最上層呼叫時的 start == 1,end == n。
然後接下來在 recursive function 裡面就需要處理兩個 base case:
start == end:比如說今天 n == 1,第一次呼叫時就會發生 start == end,這時候應該把 1 當作 root 放進答案裡,然後就回傳答案。
start > end:假設今天 start > end,那就表示上層在呼叫時,這邊的 tree 應該要沒有任何東西,所以就把 NULL 放進答案裡,回傳答案。
最後就是重點邏輯:
分別建立計算左右兩子樹的所有可能性,然後儲存在 left 跟 right 中,然後再分別組出兩邊的所有可能組合,把所有可能組合都存到 res 裡面。
實作如下:
Last updated