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

链接：

大意：

给定一个有序链表，将其转成平衡二叉树。例子：

思路：

先将链表中的值依次取出，存入数组。再对数组类似二分查找找到中间的值作为当前树的根节点，同理构造左子树和右子树。

代码：

/** * 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) {        if (head == null)            return null;        List
   
     list = new ArrayList<>();        while (head != null) {            list.add(head.val);            head = head.next;        }        Integer[] array = new Integer[list.size()];        list.toArray(array);        return buildTree(array, 0, array.length - 1);    }    public TreeNode buildTree(Integer[] array, int s, int e) {        if (s > e)            return null;        int mid = (s + e) / 2;        TreeNode root = new TreeNode(array[mid]);        root.left = buildTree(array, s, mid - 1);        root.right = buildTree(array, mid + 1, e);        return root;    }}
   

结果：

结论：

时间效率这么低.... 改进ing...

最佳：

对链表使用快慢指针找到给定区间的中间元素，这样空间复杂度即为O（1）

/** * 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) {        if(head == null)             return null;        return helper(head, null);    }    private TreeNode helper(ListNode start, ListNode end) {        if(start == null)             return null;        if(start == end)             return new TreeNode(start.val);        ListNode fast = start, slow = start, pre = null;        // 使用快慢指针找到链表在[start, end)的中间元素        while(fast != end && fast.next != end) {            fast = fast.next.next;            pre = slow;            slow = slow.next;        }        TreeNode root = new TreeNode(slow.val);        if(pre != null)            root.left = helper(start, pre);        root.right = helper(slow.next, end);        return root;    }}

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