iT邦幫忙

2025 iThome 鐵人賽

DAY 0
0
自我挑戰組

Leetcode30天挑戰系列 第 10

Day10-Convert Sorted List to Binary Search Tree

  • 分享至 

  • xImage
  •  

今天的題目為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天裡面最難的一題,可能對節點排序還不識這麼清楚。


上一篇
Day9-Convert Sorted Array to Binary Search Tree
下一篇
Day11-Balanced Binary Tree
系列文
Leetcode30天挑戰15
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言