[LeetCode] 109. Convert Sorted List to Binary Search Tree Java

题目：

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

题意及分析：将一个升序链表转化为平衡二叉搜索树。根据平衡二叉搜索树的定义，我们可以每次取出数组的中间点作为根节点，然后左边子数组的中间点作为根节点的左子节点，右边子数组的中间点作为根节点的右子节点。这里可以用两种方式，一种是遍历链表两次，将链表转化为数组，那么就变成和上一题一样了；另一种是用两个指针得到链表的中间点。

代码一（转化为数组）：

public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        int size = 0;
        ListNode count = head;
        while(count!=null){
            size++;
            count=count.next;
        }
        int[] arr = new int[size];
        ListNode getArr = head;
        int index=0;
        while(getArr!=null){
            arr[index] = getArr.val;
            getArr = getArr.next;
            index++;
        }
        return build(0,size-1,arr);
    }

    public TreeNode build(int start,int end,int[] arr){
        if(end<start) return null;
        int mid = (start+end)/2;
        TreeNode root = new TreeNode(arr[mid]);
        root.left = build(start,mid-1,arr);
        root.right = build(mid+1,end,arr);
        return root;
    }
}

代码二（直接得到链表中点）：

public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head==null) return  null;
        return build(head,null);
    }

    public TreeNode build(ListNode head,ListNode end){
        if(head==end) return null;
        ListNode fast = head;
        ListNode slow = head;

        while(fast!=end&&fast.next!=end){      //slow指向的点就是链表的中间点
            slow = slow.next;
            fast = fast.next.next;
        }
        TreeNode root = new TreeNode(slow.val);
        root.left = build(head,slow);
        root.right=build(slow.next,end);
        return root;
    }
}

[LeetCode] 109. Convert Sorted List to Binary Search Tree Java

相关推荐