将升序链表转换为平衡二叉树

---

题目描述

给定一个单链表，其中的元素按升序排序，请将它转化成平衡二叉搜索树（BST)。

解题思路

二叉搜索树的结点间是有大小排序的。即，左树任何一个结点都小于根结点，右树的任何一个结点都大于根结点。

平衡二叉树，是指左右树的深度之差小于等于1的二叉树。

其实这道题的解题思路和将升序数组转化为平衡二叉搜索树的题解题思路一样。只是，由于是不同的数据类型，在求取中点的方式不同。那么如何找到链表的中点就是这道题要解决的一个难题。

对于单链表的中点问题，可以使用快慢指针的方式：即快指针的速度永远是慢指针的两倍，当快指针到达终点时，慢指针指向的就是单链表的中点。

找到链表中点后，中点左侧就是平衡二叉搜索树的左树结点，右侧为右树结点。然后依次递归即可构造出所需的平衡二叉搜索树。

代码

// 二叉树结果和链表结构如源代码所示
class Solution
{
public:
    TreeNode* sortedListToBST(ListNode* &head)
    {
        return BST(head, NULL);
    }
private:
    TreeNode* BST(ListNode* head, ListNode* tail)
    {
        if (head == tail) // 链表为空
            return NULL;
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast != tail && fast->next != tail)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        TreeNode* root = new TreeNode(slow->val);
        root->left = BST(head, slow);
        root->right = BST(slow->next, tail);
        
        return root;
    }
};