Re: [閒聊] Grind 169

作者: Rushia (みけねこ的鼻屎)   2022-11-19 19:34:01
108. Convert Sorted Array to Binary Search Tree
給予你一個已排序的整數陣列,利用該陣列之元素構建一個平衡二元搜尋樹。
https://assets.leetcode.com/uploads/2021/02/18/btree1.jpg
Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:
https://assets.leetcode.com/uploads/2021/02/18/btree2.jpg
思路:
1.經典的分治法題目,因為題目的陣列已經排序,所以把正中間的數字當成根,較小的
數字當成左樹,較大的數字當成右樹,構建出來的數一定是一個平衡樹,因為中點的
左邊和右邊的元素數量一定是一半一半。
2.利用遞迴不斷的取中點並處理左邊和右邊的子樹即可。
JavaCode:
作者: pandix (麵包屌)   2022-11-19 19:54:00
大師

Links booklink

Contact Us: admin [ a t ] ucptt.com