LeetCode 题解
    109. Convert Sorted List to Binary Search Tree

    109. Convert Sorted List to Binary Search Tree

    有序链表转平衡二叉搜索树

    首先看到平衡，意味着我们每次都需要以链表的中点为根来构建平衡二叉搜索树

    重点：

    1. 链表找中点 -> 快慢指针

    2. 对链表进行切分 -> 保证每次递归使用快慢指针的时候能够正确地找到子链表的中点，因此需要记录一个慢指针的前继节点，方便对链表进行切割

    快慢指针模板

    ListNode *fast, *slow;
fast = slow = head;
while(fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
}
// slow 指针即为链表中点

    TreeNode* sortedListToBST(ListNode* head) {
    if (head == NULL) return NULL;
    if (head->next == NULL) return new TreeNode(head->val);

    ListNode *fast, *slow, *prev;
    fast = slow = head;
    while(fast && fast->next) {
		// 记录前继节点
        prev = slow;
        slow = slow->next;
        fast = fast->next->next;
    }
	// 切分链表
    prev->next = NULL;

    TreeNode* root = new TreeNode(slow->val);
	// 从中点左半边和右半边分别构造 BST
    TreeNode* left = sortedListToBST(head);
    TreeNode* right = sortedListToBST(slow->next);
    root->left = left;
    root->right = right;
    return root;
}

    #递归 #分治 #BST #tree

    1081. Smallest Subsequence of Distinct Characters110. Balanced Binary Tree