LeetCode[Tree]: 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.

这个链接给出了这个题目的完美解法：http://leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html

链接里有详细的介绍，有需要的话可以移步参阅。这个递归解法其实跟这个题目http://blog.csdn.net/chfe007/article/details/42153475的解题思路是一样的，只是由于链表和数组的不同导致解法上的不同。C++代码实现如下：

class Solution {
public:
    TreeNode *sortedListToBST(ListNode *head) {
        return head ? sortedListToBSTHelper(&head, , getLength(head) - ) : nullptr;
    }

private:
    int getLength(ListNode *head)
    {
        int len = ;
        for (ListNode *node = head; node != nullptr; node = node->next, ++len);
        return len;
    }

    TreeNode *sortedListToBSTHelper(ListNode **head, int start, int end)
    {
        if (*head == nullptr || end < start) return nullptr;
        int mid = (start + end) >> ;
        TreeNode *root = new TreeNode();
        root->left  = sortedListToBSTHelper(head, start, mid - );
        root->val   = (*head)->val;
        *head = (*head)->next;
        root->right = sortedListToBSTHelper(head, mid + , end);

        return root;
    }
};
           

这种解法的时间性能如下图所示：