LeetCode Convert Sorted List to Binary Search Tree 解题报告

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
从给定的有序链表生成平衡二叉树。

解题思路：最easy想到的就是利用数组生成二叉树的方法。找到中间节点作为二叉树的root节点，然后分别对左右链表递归调用分别生成左子树和右子树。时间复杂度O(N*lgN)

AC代码：

public class Solution {
    ListNode getLeftNodeFromList(ListNode head) {
        ListNode next = head;
        ListNode current = head; 
        ListNode pre = head;

        while(next!=null) {
            next = next.next;
            if(next==null) {
                break;
            }
            next = next.next;
            if(next==null) {
                break;
            }
            pre = head;
            head = head.next;
        }
        return pre;
    }
    
    
    public TreeNode sortedListToBST(ListNode head) {
        if(head==null) {
            return null;
        }
        if(head.next==null) {
            return new TreeNode(head.val);
        }
        
        ListNode left = getLeftNodeFromList(head);
        ListNode mid = left.next;
        TreeNode root = new TreeNode(mid.val);
        left.next     = null;
        root.left     = sortedListToBST(head);
        root.right    = sortedListToBST(mid.next);
        return root;
    }
}

上面的方法是一种自顶向下的方法，先找到root然后对左右子树分别递归调用。

网上又看到一种自底向上的方法。算法复杂度为O(N)。

先递归构建左子树，在构建左子树的同一时候不断移动链表的头指针，链表的头指针永远是相应当前子树位置的。

一直到左叶子节点，左叶子节点相应的就是链表的第一个元素。生成左叶子节点之后移动链表当前指针。

public class Solution {
    static ListNode currentHead = null;
    TreeNode buildTree(int start, int end) {
        if(start>end) {
            return null;
        }
        int mid = start + (end - start)/2;
        TreeNode left = buildTree(start, mid-1);
        TreeNode root = new TreeNode(currentHead.val);
        root.left = left;
        currentHead = currentHead.next;
        root.right = buildTree(mid + 1, end);
        return root;
    }
    
    public TreeNode sortedListToBST(ListNode head) {
        if(head==null) {
            return null;
        }
        currentHead = head;
        int len = 0;
        while(head!=null) {
            len++;
            head = head.next;
        }
        
        return buildTree(0, len-1);
    }
}