1008. Construct Binary Search Tree from Preorder Traversal (Medium)

寫在前面

容筆者工商一下，
「從Leetcode學演算法｜進階篇」在今天(6/9)中午12點 開放預購啦！
這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！
當中包含了面試準備須知分享 ，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！
有興趣的朋友可以使用下面的早鳥優惠～
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」 ：
https://hiskio.com/packages/YoRY45yZm

「從Leetcode學演算法」全套(基礎/進階/面試篇)同捆優惠：
https://hiskio.com/packages/MByQ4pw3W

另外，

Question

Return the root node of a binary search tree that matches the given preorder traversal.

(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value <``node.val, and any descendant of node.right has a value >``node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)

It’s guaranteed that for the given test cases there is always possible to find a binary search tree with the given requirements.

Example 1

1
2

Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

Constraints

• 1 <= preorder.length <= 100
• 1 <= preorder[i] <= 10^8
• The values of preorder are distinct.

分析/解題

從給定的前序走訪 一棵二元搜尋樹的結果，
重建一棵符合的二元搜尋樹，並回傳其根節點。
題目給出的測試資料均保證可以找到一個符合的二元搜尋樹。

我們很早以前已經解說過二元搜尋樹的特性 了，
前序走訪(preorder) 表示順序是根-左-右 ，
不像是中序走訪(inorder) 會剛好是左-根-右，順序會剛好由小到大排列 。
那麼，我們要怎麼樣才能架構一個合理的BST(二元搜尋樹)呢？
由於BST和preorder的特性，當我們一路往左走的時候，
我們會越走碰到的值越小 ，這表示我們是一路看到當下的根節點 ，
接著往左走看到左節點 才會發生這樣的狀況；

如果我們當下碰到了比根節點還要大的狀況呢？
代表這段往左已經走完了，現在看到的是右節點。
那麼怎麼知道是不是當下這個位置的右節點 呢？
我們必須要比較現在所在的位置的前面的根節點值 才行。
如果比根節點值小 ，代表它是被包含在當下這個子二元樹，
反之，則代表它應該在上一層或更上層 才對。
此外，我們可以設定一個class的變數i，
用來紀錄現在我們建立二元樹的過程走到哪個index。

那麼我們來整理一下流程：
0. 初始化一個class變數 i = 0 。

1. 先檢查當前的陣列/串列是不是沒東西 ，沒東西的話就回傳null/None。
2. 將int的最大值 作為邊界值 bound，
   傳入用來建立二元樹的函式(這裡命名為build )
3. 在build函式中，檢查如果i走完全長了 或者preorder[i] > bound，
   前者表示整個樹重建完了，後者表示這個子樹底下對於preorder[i]來說不可能放在任何一個地方了，所以回傳null/None回到上一層。4. 在這層建立一個 根節點root，** 其值為preorder[i]，完成後 將i遞增**。
4. 接下來要建立root.left，呼叫build函式，
   將preorder及邊界值root.val 傳入。
   (因為root的左子樹所有值都要小於root的值)
5. 再來建立root.right，呼叫build函式，
   將preorder及邊界值bound傳入。
   (因為root的右子樹裡的所有值要介於root的值 和上一層限制的bound 之間)
6. 這層等於建立完畢了，將root回傳 。

我們簡單拿Example 1為範例來嘗試推導看看：

1. (i, preorder[i], bound) = (0, 8, Integer.MAX_VALUE)
   => root節點建立，其值為8，i遞增，呼叫build(preorder, 8)以建立左節點。

2. (i, preorder[i], bound) = (1, 5, 8)
   => 建立根節點，其值為5，i遞增，呼叫build(preorder, 5)以建立左節點。

3. (i, preorder[i], bound) = (2, 1, 5)
   => 建立根節點，其值為1，i遞增，呼叫build(preorder, 1)以建立左節點。

4. (i, preorder[i], bound) = (3, 7, 1)
   => 7>1，所以表示這層沒辦法放了，回傳null到上一層。

5. (i, preorder[i], bound) = (3, 7, 5)
   => 走到root.right這行，呼叫build(preorder, 8)以建立右節點。

6. (i, preorder[i], bound) = (3, 7, 8)
   => 建立根節點，其值為7，i遞增，
   呼叫root.left及root.right兩行都會回傳null，
   所以回傳該節點到上一層。

7. (i, preorder[i], bound) = (4, 10, 8)
   => 在5的底下建立完7的右節點了，這邊也完成了，
   回傳5的節點回到上一層。

8. (i, preorder[i], bound) = (4, 10, Integer.MAX_VALUE)
   => 走到root.right這行，呼叫build(preorder, Integer.MAX_VALUE)。

9. (i, preorder[i], bound) = (4, 10, Integer.MAX_VALUE)
   => 建立根節點，其值為10，i遞增，
   root.left這行會回傳null，
   root.right傳入build(preorder, Integer.MAX_VALUE)。

10. (i, preorder[i], bound) = (5, 12, Integer.MAX_VALUE)
    => 建立根節點，其值為12，i遞增。

11. 後面的部分由於i已經到達6，所以會往上層回到8的這層，
    最後回傳根節點(值為8)，結束。

請讀者嘗試在紙上畫出來推過一遍，有助於更了解整個程式運行。
由於我們是先一路往左深入並建立節點，碰到無法建立時，
才回到上一層並嘗試往右走，
所以這樣子的方式是DFS(深度優先搜尋) 的模式。

依此，寫成程式碼如下：

Java

Java的部分，
使用int時可以用Integer.MAX_VALUE作為初始邊界(即int能表示的最大值)。

Python

Python的部分，我們可以設定bound在未傳入值時預設值當作float(‘inf’) ，
即可使用同一個函式進行遞迴。
此外，還是不要忘記Python並沒有++或–，請自己換成用**”self.i += 1"** 。

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

「時間/空間複雜度？」
(O(length of array)/O(1), 如果計算call stack的話則是O(BST的深度))

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

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

另外，「從Leetcode學演算法｜基礎篇」已經回原價囉，
先前的優惠碼會失效，但這邊仍然為讀者保留了300塊的折抵，
雖然整捆一起買總體比較划算(差290而已就有整組了阿XD)，
如果你還是想先試試基礎課的話，
300元折抵的連結 在這邊： https://hiskio.com/courses/319?promo_code=NEXLJXE