0108. Convert Sorted Array to Binary Search Tree (Easy)
Question
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than 1.
Example:
| |
| |
| |
分析/解題
給定一個陣列，其元素以升冪排序 (也就是後面的一定比前面大)，
試將其轉成一個高度平衡的二元搜尋樹。
高度平衡的樹由於已在先前的題目中講過了(0110. Balanced Binary Tree)，
這邊就不再贅述，簡言之就是對每個節點，
其兩邊的子樹深度相差均<=1就對了！
我們知道要達到這個條件，最基本的就是一個root的左右兩邊要公平，
所以最簡單的作法就是取中位數作為根，其左邊就是左子樹的所有節點，
右邊就是右子樹的所有節點；再分別讓各自的左右子樹再次拆分，直到分到沒有節點為止。
這樣作可以讓每一層都均分節點，從而讓每個分支的深度基本接近一致。
故整體流程如下：
- 檢查陣列是否是空的或者null，是的話直接回傳
- 呼叫一個用來遞迴建立BST的函式，這邊命名成getNode()
- getNode會輸入陣列以及當下的左右邊界(nums, l, r)
(一開始l = 0, r = N-1, N是nums的總數) - 每次先檢查左右邊界是否黃金交叉(表示已經完成了，可以回傳null)
- 讓mid = l加r的一半，直接建立一個root節點
- root節點的左節點 就應該是呼叫getNode(nums, l, mid-1) 得到的結果
- root節點的右節點 則會是getNode(nums, mid+1, r) 得到的結果
- 回傳root
我們可以看到每次會抓中間值產生一個節點，再利用已排序的特性，
繼續進入遞迴往下將左邊和右邊的節點處理完畢。
思考它的執行流程，應該會發現總體而言我們會先一路來到最左邊的節點，
再回頭建立每個遞迴函式的右邊節點；
也就是說，程式執行的優先順序是先往深處的方向走 而非先將這一層的狀況處理完，這種模式我們稱之為深度優先搜尋(Depth-First Search, DFS) ；
如果換作是優先順序是先廣泛地處理完這一層，再往下一層走 ，這種模式就稱之為廣度優先搜尋(Breadth-First Search, BFS) 。
程式碼的部分，僅需留意Java因為想避免overflow的狀況，
計算的方式為 start + (end - start) / 2 ，而非(start + end) / 2。
Java
Python
面試實際可能會遇到的問題
「時間/空間複雜度？」
(O(N), O(N)
每個節點都會掃過一遍，且基本和其他節點沒有太多連帶關係。)
「那麼如果要將一個BST轉成排序陣列 呢？」
(原則上可用Inorder Traversal ，
但留意不加NIL的狀況其實中間樹的架構資訊可能會就此流失掉)
相似及延伸
- 0109. Convert Sorted List to Binary Search Tree (起始給的從陣列/串列改成排序好的LinkedList)
Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)
從LeetCode學演算法，我們下次見囉，掰~