今天的題目為109.Convert Sorted List to Binary Search Tree,而今天的題目是再叫我們將排序好的單向鏈結串列轉換成高度平衡的二元搜尋樹。
以下是程式碼與講解:
class Solution {
public TreeNode sortedListToBST(ListNode head) {
// 建立一個 ArrayList 來儲存鏈結串列的所有值
List<Integer> values = new ArrayList<>();
while (head != null) {
values.add(head.val); // 將每個節點的值加入陣列
head = head.next; // 移動到下一個節點
}
// 使用遞迴方式,根據陣列建構 BST
return buildTree(values, 0, values.size() - 1);
}
private TreeNode buildTree(List<Integer> values, int left, int right) {
// 遞迴終止條件:區間無效
if (left > right) return null;
// 找出中間位置,作為根節點(確保平衡)
int mid = left + (right - left) / 2;
TreeNode node = new TreeNode(values.get(mid)); // 建立根節點
// 遞迴建立左子樹(左半邊陣列)
node.left = buildTree(values, left, mid - 1);
// 遞迴建立右子樹(右半邊陣列)
node.right = buildTree(values, mid + 1, right);
return node; // 回傳建好的子樹
}
}
今天的是我覺得這10天裡面最難的一題,可能對節點排序還不識這麼清楚。