LeetCode-109.有序链表转换二叉搜树

二叉搜索树

二叉查找树又称二叉搜索树或者二叉排序树；它可以是一个空树或者是一个二叉树，既有链表的快速插入与删除的特点，又有数组快速查找的优势。具有以下性质：
①．若左子树非空，则左子树所有节点均小于根节点的值；
②．若右子树非空，则右子树所有节点均大于根节点的值；
③．左右子树也是二叉查找树；
④．没有键值相等的节点。

快慢指针

快慢指针是两个指针同向移动，某一时刻来看两个指针一个在前，一个在后，即快指针和慢指针。造成两个指针一前一后的原因有两种情况：
①．两个指针速度相同，但是出发时间不同，也可以认为是出发起始位置不同，在两个指针都出发后会以固定的距离间隔一前一后的向前移动；
②．两个指针速度不同，但是从同一个起点同时出发，之后会以固定的速度差一前一后的向前移动，两个指针的距离间隔随时间规律的递增；

题目分析

①．原链表是有序的，要使转换成的二叉树高度平衡，只需要寻找中间节点作为跟节点即可，然后作用两侧分别转换成左子树和右子树。
②．查找中间节点可以使用快慢指针进行查找。
③．通过递归算法即可完成二叉搜索树的转换。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {

        return sortedListToBST(head,nullptr);

    }
    // [head,tail) 左闭右开范围
    TreeNode* sortedListToBST(ListNode* head,ListNode *tail)
    {
        //遍历到了尾节点，直接返回
        if( head == tail ) return nullptr;
        //查找当前范围的中间节点作为根节点
        ListNode *mid = midNode(head,tail);
        if( mid == nullptr ) return nullptr;

        TreeNode * root = new TreeNode();
        root->val = mid->val;
        //当前范围只剩一个节点，终止递归
        if( head == mid ) return root;
        //递归得到左右子节点
        root->left = sortedListToBST(head,mid);
        root->right = sortedListToBST(mid->next,tail);

        return root;
    }
    //双指针查找链表中间节点
    ListNode* midNode(ListNode* head,ListNode * tail)
    {
        ListNode * fast = head, *slow = head;
        while(fast != tail && fast->next != tail)
        {
            slow = slow->next;
            fast = fast->next;
            fast = fast->next;
        }
        return slow;
    }

};