LeetCode——将有序链表转换为二叉搜索树

NO.109 将有序链表转换为二叉搜索树中等

思路一：中序遍历还原 这道题和NO.108属于姊妹题，同样是通过明确的遍历序列还原二叉树。

所以说可以使用相同的思路，中点确定根，从而确定左右子树，递归出口也是区间内没有元素。

本题的难点在于参数是一个链表，不能像数组一样随机访问。

找链表最笨的方法就是两次遍历，第一次算节点个数，第二次找到中点。

通常这样的问题都可以使用快慢指针来解决，快指针一次走两步，慢指针一次走一步，当快指针走完区间，慢指针就刚好到达区间的1/2处。

//快慢指针找中点
ListNode fast = head, slow = head;
while (fast != tail && fast.next != tail) {
    fast = fast.next.next;
    slow = slow.next;
}

PS：本题递归函数传参形成的区间是前闭后开的，所以左右端点相等就表示区间内没有元素。

public TreeNode sortedListToBST(ListNode head) {
    if (head == null) return null;
    return buildBST(head, null);
}

private TreeNode buildBST(ListNode head, ListNode tail) {
    //出口
    if (head == tail) return null;
    //快慢指针找中点
    ListNode fast = head, slow = head;
    while (fast != tail && fast.next != tail) {
        fast = fast.next.next;
        slow = slow.next;
    }
    //slow指向链表中点，生成根节点
    TreeNode root = new TreeNode(slow.val);
    //生成左右子树
    root.left = buildBST(head, slow);
    root.right = buildBST(slow.next, tail);
    return root;
}

时间复杂度：O(nlogn) 每个元素需要访问一次生成树节点，每次生成树节点的时候都需要快慢指针找中点是个O(logn)。

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.109 将有序链表转换为二叉搜索树 中等

NO.109 将有序链表转换为二叉搜索树中等