前往
大廳
主題

LeetCode - 109. Convert Sorted List to Binary Search Tree 解題心得

Not In My Back Yard | 2021-05-18 00:00:05 | 巴幣 2 | 人氣 308

題目連結:


題目意譯:
給定一個單向連結串列(Linked List)的頭 head ,其元素按照升序排列,將其轉換為一個平衡高度(Height-Balanced)二元搜尋樹(Binary Search Tree,BST)。

對於此問題,一個平衡高度二元樹定義為:對於一棵二元樹中任何節點,其兩棵子樹之深度差不超過 1 。

限制:
head 之節點數介於範圍 [0, 2 × 104] 中。
-10 ^ 5 ≦ Node.val ≦ 10 ^ 5



範例測資:
範例 1:
輸入: head = [-10,-3,0,5,9]
輸出: [0,-3,9,-10,null,5]
解釋: 一個可能的答案為 [0,-3,9,-10,null,5],其代表著圖示的平衡高度二元搜尋樹。

範例 2:
輸入: head = []
輸出: []

範例 3:
輸入: head = [0]
輸出: [0]

範例 4:
輸入: head = [1,3]
輸出: [3,1]


解題思維:
先將給定的連結串列之內容轉存到一個新的陣列裡。然後利用這題的方式將陣列轉換為所求的平衡高度二元搜尋樹。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作