题目要求

• 给定一个升序的单链表，将其转换为一颗平衡查找树
• 举例：给定链表[-10,-3,0,5,9],转换为[0,-3,9,-10,null,5]或者其他平衡查找树

解题思路

• 平衡查找树是需要左子树比根节点小，右子树比根节点大形成的一棵树
• 可以利用这个特性进行递归构造，首先是我们找到一个链表中的中间节点，然后这个中间节点作为根节点，中间节点左侧为左子树，右侧为右子树进行递归构建，当这个分段为null或者起始节点和终止节点相等此时就作为递归返回条件
• 查找链表中间节点：可以采用一步和两步索引法，一个变量mid遍历链表每次走一个节点，另一个变量temp一次走两个节点，当temp走到链表尾时，mid刚好走到链表中间。
• 然后按照这个mid构造平衡查找树

源代码实现(非本人实现，学习的他人解法)

/**
 * 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; }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        return helper(head, null);
    }
    
    private TreeNode helper(ListNode head, ListNode last) {
        if (head == null || head == last) return null;
        ListNode mid = head, temp = head;
        //寻找中间节点
        while (temp != last && temp.next != last) {
            mid = mid.next;
            temp = temp.next.next;
        }
        TreeNode root = new TreeNode(mid.val);
        root.left = helper(head, mid);
        root.right = helper(mid.next, last);
        return root;
    }
}