本文共 2469 字，大约阅读时间需要 8 分钟。

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

我的想法

二分，根结点是每段的中点。但是因为给的是一个linkedlist，不好分段访问，每次都得从头遍历。但是直接用for循环把linkedlist换成array感觉又失去了这道题的意义。

class Solution {
       public TreeNode sortedListToBST(ListNode head) {
           if(head == null) {
               return null;        }        ListNode cur = head;        int end = 0;        while(cur != null) {
               end++;            cur = cur.next;        }        int mid = end / 2;        ListNode node = getNode(mid, head);        TreeNode root = new TreeNode(node.val);        helper(0, mid, head, root);        helper(mid + 1, end, head, root);        return root;    }    private void helper(int start, int end, ListNode head, TreeNode root) {
           if(end - start <= 0) {
               return;        }        int mid = start + (end - start) / 2;        ListNode node = getNode(mid, head);        TreeNode newRoot = new TreeNode(node.val);        if(node.val > root.val) {
               root.right = newRoot;        } else {
               root.left = newRoot;        }        helper(start, mid, head, newRoot);        helper(mid + 1, end, head, newRoot);    }    private ListNode getNode(int index, ListNode head) {
           ListNode res = head;        while(index > 0) {
               res = res.next;            index--;        }        return res;    }}

解答

jiuzhang solution:

public class Solution {
       private ListNode current;    private int getListLength(ListNode head) {
           int size = 0;        while (head != null) {
               size++;            head = head.next;        }        return size;    }    public TreeNode sortedListToBST(ListNode head) {
           int size;        current = head;        size = getListLength(head);        return sortedListToBSTHelper(size);    }    public TreeNode sortedListToBSTHelper(int size) {
           if (size <= 0) {
               return null;        }                TreeNode left = sortedListToBSTHelper(size / 2);        TreeNode root = new TreeNode(current.val);        current = current.next;        TreeNode right = sortedListToBSTHelper(size - 1 - size / 2);        root.left = left;        root.right = right;        return root;    }}

转载地址：http://byqvb.baihongyu.com/