[LeetCode] 108. Convert Sorted Array to Binary Search Tree

轉自LeetCode

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

<Solution>

這題是要將 sorted array 轉換成 BST

從 BST 的特性可以知道，root 會是在 sorted array 中間的那個數

然後再分成左半部和右半部，分別是左子樹和右子樹

而在 BST 中，左子樹和右子樹也都還會是 BST

所以這題就是一道二分法的題目，只是不是搜尋，而是建 BST 而已

code 如下
c++

kotlin
還有 iterative 的做法 (參考資料)

想法如下

• 一樣是使用二分法的概念，只是用一個 queue 將 left index 和 right index 存起來，然後依序處理

• 配合上面步驟存的 index，也用一個 queue 將對應的 node 存起來

• 根據 left index 和 right index，把對應的值給對應的 node

code 如下

可以使用 C++11 引入的 tuple 來改寫 iterative 的解法，這樣就不需要兩個 queue 了

code 如下