LeetCode - 109. Convert Sorted List to Binary Search Tree

同樣是建構平衡的BST，這道題目的思路與上一題是一樣的，都是通過遞歸調用的方式逐漸找到每一個子樹的root，然後添加左子樹和右子樹。因為這裡數字的載體由array變成了linked list，是以也變得更加複雜起來，最重要的就是在給出一個頭節點和尾節點，找到mid結點的方法，這個可以使用fast/slow runnner來實作。時間複雜度為O(n)，代碼如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode buildBST(ListNode start, ListNode end){
        if(start == end) return null;
        
        // Initialize fast/slow runners
        ListNode slow = start;
        ListNode fast = start;
        
        // Find middle node
        while(fast != end && fast.next != end){
            fast = fast.next.next;
            slow = slow.next;
        }
        
        // Construct BST
        TreeNode root = new TreeNode(slow.val);
        root.left = buildBST(start, slow);
        root.right = buildBST(slow.next, end);
        
        return root;
    }
    
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        
        return buildBST(head, null);
    }
}
           

知識點：

1. 在一個Linked List中，給定一個head和tail，找到mid節點的方法->使用fast/slow runner，這個基礎的問題要記住

2. 從一列數中建構balanced BST的方法：首先進行sort，然後逐漸從這一列數中找到中間的數字作為root，繼而遞歸地在左部分和右部分尋找

3. 遞歸思想的使用，在遞歸函數的參數清單和給出的原型函數的參數清單不一緻的時候，可以另外寫一個函數進行遞歸調用