leetcode-convert-sorted-list-to-balanced-tree

题目大意

　　https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

　　将一个有序链表转换成一颗平衡二叉树

题目分析

　　由于是链表，因此不能随机访问某个index的值。考虑用递归的方法做，注意到有序链表的序列实际上是二叉树的中序遍历的结果。可以定义一个根据头节点获取链表长度的方法，再定义一个全局的下次作为head点的指针，关键在于sortedListToBST中递归的思路不是很容易想，具体可以看下代码。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private static ListNode h;
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) {
            return null;
        }
        h = head;
        return sortedListToBST(0, getLength(head) - 1);
    }
    
    public static int getLength(ListNode head) {
        int len = 0;
        while(head != null) {
            head = head.next;
            len++;
        }
        return len;
    }
    
    public static TreeNode sortedListToBST(int start, int end) {
        if (start == end) { // 如果只有一个元素，直接构建返回
            int v = h.val;
            h = h.next;
            return new TreeNode(v);
        }
        if (start > end) {   // 直接返回null
            return null;
        }
        int mid = (start + end) / 2;
        TreeNode left = sortedListToBST(start, mid - 1);
        TreeNode root = new TreeNode(h.val);
        h = h.next; // 全局指针，每次后移一个
        TreeNode right = sortedListToBST(mid + 1, end);
        root.left = left;
        root.right = right;
        return root;
    }
}