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. 递归思想的使用，在递归函数的参数列表和给出的原型函数的参数列表不一致的时候，可以另外写一个函数进行递归调用