【Day 9 】2021-12-20 - 109. 有序链表转换二叉搜索树

[azl397985856]

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

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/

前置知识

• 递归
• 二叉搜索树的任意一个节点，当前节点的值必然大于所有左子树节点的值。同理,当前节点的值必然小于所有右子树节点的值

  题目描述

  
  给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

  0
 / \

-3 9 / / -10 5

[yan0327]

思路： 高度平衡二叉树 =》意味着左右子树的深度都相同 =》分治算法 参考链表归并排序的实现思路。并且用递归实现 关注两个关键节点：1.如果是nil，则直接返回nil 2. 如果链表只有一个节点，则直接作为值返回叶节点。 其次就是： 快慢指针找中点，同时用一个前驱节点pre保存前一个结点待访问。 找到中点后注意两个关键环节， 第一个关键环节前驱结点pre.Next = nil 断开 第二个关键环节为slow.Next作为输入参数。 然后就是常规的把slow【中间结点】作为根结点的值， 左叶子节点的值取决于 前半部分的链表递归值 右叶子节点的值取决于 后半部分的链表递归值 答案完毕。

func sortedListToBST(head *ListNode) *TreeNode {
    if head == nil{
        return nil
    }
    pre := &ListNode{Next:head}
    if head.Next == nil{
        return &TreeNode{Val:head.Val}
    }
    slow := head
    fast := head
    for fast!= nil && fast.Next!= nil{
        pre = slow
        slow = slow.Next
        fast = fast.Next.Next
    }
    pre.Next = nil
    root := &TreeNode{Val:slow.Val}
    root.Left = sortedListToBST(head)
    root.Right = sortedListToBST(slow.Next)
    return root
}

时间复杂度：O（n*logn）分治 空间复杂度：O（logn）

[CodeWithIris]

Note (Recursion)

• The median is found by the fast and slow Pointers, and the median is used as the child root node.
• The left part of the median is its left subtree, and the right part is its right subtree.

Solution (C++)

class Solution {
public:
    TreeNode* buildTree(ListNode* left, ListNode* right){
        if(left == right) return nullptr;
        ListNode* slow = left;
        ListNode* fast = left;
        while(fast != right && fast->next != right){
            slow = slow->next;
            fast = fast->next->next;
        }
        TreeNode* node = new TreeNode(slow->val);
        node->left = buildTree(left, slow);
        node->right = buildTree(slow->next, right);
        return node;
    }
    TreeNode* sortedListToBST(ListNode* head) {
        return buildTree(head, nullptr);
    }
};

Complexity

• T: O(nlogn)
• S: O(logn), the height of the binary search tree is O(logn).

[chakochako]

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        def getLength(head: ListNode) -> int:
            ret = 0
            while head:
                ret += 1
                head = head.next
            return ret

        def buildTree(left: int, right: int) -> TreeNode:
            if left > right:
                return None
            mid = (left + right + 1) // 2
            root = TreeNode()
            root.left = buildTree(left, mid - 1)
            nonlocal head
            root.val = head.val
            head = head.next
            root.right = buildTree(mid + 1, right)
            return root

        length = getLength(head)
        return buildTree(0, length - 1)

[Courtneyz94]

def sortedListToBST(self, head):
    if not head:
        return 
    if not head.next:
        return TreeNode(head.val)
    slow, fast = head, head.next.next
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
    tmp = slow.next
    slow.next = None
    root = TreeNode(tmp.val)
    root.left = self.sortedListToBST(head)
    root.right = self.sortedListToBST(tmp.next)
    return root

[SenDSproject]

解题思路：抄的答案，需要注意后面指针的用法 老是写错

   class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:

        if not head:
            return head
        pre, slow, fast = None, head, head

        while fast and fast.next:
            fast = fast.next.next
            pre = slow
            slow = slow.next
        if pre:
            pre.next = None
        node = TreeNode(slow.val)
        if slow == fast:
            return node
        node.left = self.sortedListToBST(head)
        node.right = self.sortedListToBST(slow.next)
        return node

时间复杂度 O(N)
空间复杂度O（N)

[for123s]

代码

• 语言支持：C++

C++ Code:

/**
 * 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 {
    vector<int> nums;
public:
    TreeNode* buildTree(int l,int r)
    {
        if(l>r)
            return nullptr;
        int mid = (l+r+1)/2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = buildTree(l,mid-1);
        root->right = buildTree(mid+1,r);
        return root;
    }
    TreeNode* sortedListToBST(ListNode* head) {
        int l = 0;
        while(head)
        {
            nums.push_back(head->val);
            head = head->next;
        }
        return buildTree(0,nums.size()-1);
    }
};

[wxj783428795]

思路

1.找到中间节点作为二叉树的根节点。 2.找到根节点左侧链表的中间节点作为根节点左侧子树的根节点，右侧同理 3.循环以上步骤

代码

var sortedListToBST = function (head) {
    if (!head) return null;
    return dfs(head, null);
};

var dfs = (head, tail) => {
    if (head === tail) return null;
    let fast = head;
    let slow = head;
    while (fast !== tail && fast.next !== tail) {
        fast = fast.next.next;
        slow = slow.next;
    }
    let root = new TreeNode(slow.val, dfs(head, slow), dfs(slow.next, tail));
    return root;
}

复杂度分析

复杂度分析不是很会，不一定对，如果有错，请指正。

• 时间复杂度：O(nlogn)
• 空间复杂度：O(logn)

[yetfan]

思路 快慢指针找根节点，然后左链表断开 继续找左子树，右链表继续找右子树

代码

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        if not head:
            return None

        slow = head
        fast = head
        pre = None

        while fast and fast.next:
            pre = slow
            slow = slow.next
            fast = fast.next.next

        root = TreeNode(slow.val)
        print(slow.val)
        if pre:
            pre.next = None
            root.left = self.sortedListToBST(head)

        root.right = self.sortedListToBST(slow.next)

        return root

复杂度 时间O(nlogn) 空间O(logn)

[Yutong-Dai]

class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        self.num_array = []
        while head:
            self.num_array.append(head.val)
            head = head.next
        num_elements = len(self.num_array)
        root = self.helper(0, num_elements-1)
        return root

    def helper(self, start, end):
        if start == end:
            return TreeNode(self.num_array[start], left= None, right=None)
        if start > end:
            return None
        mid_point = (end + start) >> 1
        root = TreeNode(self.num_array[mid_point], left= None, right=None)
        root.left = self.helper(start, mid_point-1)
        root.right = self.helper(mid_point+1, end)
        return root

[zhangzz2015]

思路

• 方法1，可把链表转换为vector 。通过vector 来生成平衡二叉搜索树。时间复杂度为O(n)，空间复杂度为O(n)。

• 方法2，进一步优化方法1的内存，先遍历链表，拿到总的size，可通过模拟中序遍历，来生成平衡二叉搜索树，则遍历顺序和链表的顺序相同。时间复杂度为O(n)，空间复杂度为 O(log N)，为递归树的深度。

  关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        // method 1. Convert List to vector. Then generate. 

        if(head == NULL)
            return NULL; 
        vector<int> record; 
        while(head)
        {
            record.push_back(head->val); 
            head =head->next; 
        }

        return dfs(record, 0, record.size()-1);
    }

    TreeNode* dfs(vector<int>& record, int start, int end)
    {
        if(start>end)
            return NULL; 
        int middle = start + (end - start)/2; 

        TreeNode* current = new TreeNode(record[middle]); 

        current->left = dfs(record, start, middle-1); 
        current->right =dfs(record, middle+1, end); 

        return current; 

    }
};

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        // method 1. Convert List to vector. Then generate. 

        if(head == NULL)
            return NULL; 
        int size =0;
        ListNode* current = head; 
        while(current)
        {
            size++; 
            current =current->next; 
        }

        return dfs(head, 0, size-1);
    }

    TreeNode* dfs(ListNode* & head, int start, int end)
    {
        if(start>end)
            return NULL; 
        int middle = start + (end - start)/2; 

        TreeNode* nodeleft = dfs(head, start, middle-1);
        TreeNode* current = new TreeNode(head->val);
        head = head->next; 
        TreeNode* noderight =dfs(head, middle+1, end); 
        current->left = nodeleft; 
        current->right = noderight; 
        return current; 

    }
};

[zwmanman]

思路

1.fast and slow node to find mid point 2.left will be left tree and right will be right tree

class Solution(object): def sortedListToBST(self, head): """ :type head: ListNode :rtype: TreeNode """ if not head: return None

    return self.dfs(head, None)

def dfs(self, head, tail):
    if head == tail:
        return None
    slow = head
    fast = head

    while fast != tail and fast.next != tail:
        slow = slow.next
        fast = fast.next.next

    root = TreeNode(slow.val)
    root.left = self.dfs(head, slow)
    root.right = self.dfs(slow.next, tail)
    return root

[CoreJa]

思路

题目和108很类似，四个方法，

• naive思路：遍历链表找中点，把链表截断分成左中右，递归构造树，复杂度O(nlogn)，慢在每次要遍历链表
• 参考的思路：链表顺序和树中序遍历结果相同。可以根据链表长度提前把树构造好，直接中序遍历树填空即可。复杂度O(n)
• 上述优化：不再提前把树建好，而是用left和right来找到边界，边遍历边建树
• 偷懒思路：把链表变成列表，可以在O(1)找到中点。

代码

class Solution:
    # naive思路，遍历链表找中点，把链表截断分成左中右，递归构造树，
    # 复杂度O(nlogn)，慢在每次要遍历链表
    def sortedListToBST1(self, head: ListNode) -> TreeNode:
        if head is None:
            return None
        if head.next is None:
            return TreeNode(head.val)
        mid = end = head
        mid_pre = None

        while end and end.next:
            mid_pre = mid
            mid = mid.next
            end = end.next.next

        root = TreeNode(mid.val)
        if mid_pre:
            mid_pre.next = None
        root.left = self.sortedListToBST1(head)
        root.right = self.sortedListToBST1(mid.next)

        return root

    # 题解思路，根据链表长度提前把树构造好，直接中序遍历树填空即可
    # 因为链表顺序和中序遍历结果相同。复杂度O(n)
    def sortedListToBST2(self, head: ListNode) -> TreeNode:
        p = head
        cnt = 0
        while p:
            cnt += 1
            p = p.next
        if cnt == 0:
            return None
        root = TreeNode()
        nodes = deque([root])
        i = 1
        while i < cnt:
            node = nodes.popleft()
            if i < cnt:
                node.left = TreeNode()
                nodes.append(node.left)
                i += 1
            if i < cnt:
                node.right = TreeNode()
                nodes.append(node.right)
                i += 1
        cur = head

        def mid_traverse(node):
            nonlocal cur
            if node.left:
                mid_traverse(node.left)
            node.val = cur.val
            cur = cur.next
            if node.right:
                mid_traverse(node.right)

        mid_traverse(root)
        return root

    # 上述方法的优化，不再提前把树建好，而是边遍历边建
    def sortedListToBST3(self, head: ListNode) -> TreeNode:
        cnt = 0
        p = head
        while p:
            cnt += 1
            p = p.next

        def build(left, right):
            if left > right:
                return None
            mid = (left + right) // 2
            root = TreeNode()
            root.left = build(left, mid - 1)
            nonlocal p
            root.val = p.val
            root.right = build(mid + 1, right)
            return root

        p = head
        return build(0, cnt - 1)

    # 偷懒思路，把链表转成列表，再套用上面的方法，O(n)
    def sortedListToBST4(self, head: ListNode) -> TreeNode:
        p = head
        arr = []
        while p:
            arr.append(p.val)
            p = p.next

        def merge(arr):
            if len(arr) == 0:
                return None
            mid = len(arr) // 2
            root = TreeNode(arr[mid])
            root.left = merge(arr[:mid])
            root.right = merge(arr[mid + 1:])
            return root

        return merge(arr)

[ForLittleBeauty]

思路

---

1. find the mid node, make it the tree root
2. Make the left of the mid node to be the left child of the tree
3. do the same to the right
4. Do it recursively

---

代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        if not head:
            return None
        if not head.next:
            return TreeNode(head.val)

        def findMid(head):
            slow = fast = head
            prev = None
            while fast and fast.next:
                prev = slow
                slow = slow.next
                fast = fast.next
                if fast.next:
                    fast = fast.next
            prev.next = None
            return slow

        mid = findMid(head)
        root = TreeNode(mid.val)
        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(mid.next)
        return root

---

时间复杂度: O(nlogn)

空间复杂度: O(logn)

[laofuWF]

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        if not head: return None
        if not head.next: return TreeNode(head.val)

        prev = head
        slow = head
        fast = head
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next

        node = TreeNode(slow.val)
        left = head
        right = slow.next
        prev.next = None

        node.left = self.sortedListToBST(left)
        node.right = self.sortedListToBST(right)

        return node

[Tao-Mao]

Idea

Use slow/fast pointers to get node in the middle, and refer to it as the root node of the treenode. Recursively doing the process.

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return new TreeNode(head.val);
        ListNode slow = head;
        ListNode fast = head;
        ListNode tmp = slow;
        // System.out.print(tmp);
        while (fast != null && fast.next != null) {
            tmp = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        tmp.next = null;
        // System.out.println(slow.val);
        TreeNode res = new TreeNode(slow.val);
        res.right = sortedListToBST(slow.next);
        res.left = sortedListToBST(head);

        return res;

    }
}

Complexity

Time: O(nlogn) Space: O(logn)

[zjsuper]

def sortedListToBST4(self, head: ListNode) -> TreeNode:
    p = head
    arr = []
    while p:
        arr.append(p.val)
        p = p.next

    def merge(arr):
        if len(arr) == 0:
            return None
        mid = len(arr) // 2
        root = TreeNode(arr[mid])
        root.left = merge(arr[:mid])
        root.right = merge(arr[mid + 1:])
        return root

    return merge(arr)

[Grendelta]

思路

使用快慢指针实现二分，然后进行递归。

代码

    if not head:
        return head
    pre, slow, fast = None, head, head

    while fast and fast.next:
        fast = fast.next.next
        pre = slow
        slow = slow.next
    if pre:
        pre.next = None
    node = TreeNode(slow.val)
    if slow == fast:
        return node
    node.left = self.sortedListToBST(head)
    node.right = self.sortedListToBST(slow.next)
    return node

复杂度

时间复杂度O(N)

空间复杂度O(N)

[wenjialu]

thought

函数：构造树 …递归函数返回条件… 找中点 以中点为root = TreeNode（）
 lt = 中点前链表构建树 （调用函数 Rt = 中点后链表构建树 （调用函数 root.left = lt Root.right = rt 返回 root

code

class Solution: def sortedListToBST(self, head: ListNode) -> TreeNode:

mid node as head, construct a tree.

    # store 2 list in two stack. (wrong, 不需要把节点存stack里面)
    #  我只要把中点找到，然后把左半部分链表传到构造树的函数里面，右半部分链表传到构造树的函数里面。
    #  root.left = 左半部分链表排好的。root.right = 右半部分链表排好的。
    slow, fast  = head, head
    pre = None

    # omg, 递归的边界条件又忘了。。。。递归三要素！！
    if not head:
        return
    if not head.next: # 叶子节点，返回它自己！！
        return TreeNode(head.val) # ??? #解决33行Nonetype has no attribute 问题。

    while fast and fast.next:
        pre = slow # 记录slow前一个，也就是前半段链表的最后一个节点。
        slow = slow.next
        fast = fast.next.next
    # print(slow.val,left_stack)
    # print(pre, slow.val, fast.val)
    pre.next = None
    root = TreeNode(slow.val) # 每次递归都要TreeNode吗？？？
    left_tree = self.sortedListToBST( head )
    right_tree = self.sortedListToBST( slow.next )
    root.left = left_tree
    root.right = right_tree
    return root

com

时间复杂度：O(nlogn)，其中 nn 是链表的长度。 设长度为 nn 的链表构造二叉搜索树的时间为 T(n)???，递推式为 T(n) = 2 \cdot T(n/2) + O(n)T(n)=2⋅T(n/2)+O(n)，根据主定理，T(n) = O(n \log n)T(n)=O(nlogn)。

空间复杂度：O(\log n)O(logn)，这里只计算除了返回答案之外的空间。平衡二叉树的高度为 O(\log n)O(logn)，即为递归过程中栈的最大深度，也就是需要的空间。

[Alexno1no2]

分析： 特里处理：如果head为空返回空，如果head.next为空返回值为head.val的树节点 用快慢指针找链表中间节点（slow每次走一步，fast每次走两步，循环停止时slow指向中间节点） 找中间节点时记录一下slow的前一个节点pre，后面将链表分成前后两部分时有使用到 创建树的根节点，把slow的值赋给它，并断开链表中间节点和左边子链表的连接 递归链表中间节点左右两边的子链表，找子链表的中间节点，再找子链表的子链表的中间节点，如此循环往复，直到符合特例处理的条件递归返回 复杂度： 时间复杂度：O(nlogn)，每次递归找中点O(n)，递归次数O(logn) 空间复杂度：O(logn)，平衡二叉树的高度O(logn)

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        if not head:
            return None
        elif not head.next:
            return TreeNode(head.val)

        pre, slow, fast = None, head, head
        while fast and fast.next:
            pre = slow
            slow = slow.next
            fast = fast.next.next

        root = TreeNode(slow.val)
        pre.next = None

        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(slow.next)
        return root

[SHAO-Nuoya]

Code

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        def getMedian(left: ListNode, right: ListNode) -> ListNode:
            fast = slow = left
            while fast != right and fast.next != right:
                fast = fast.next.next
                slow = slow.next
            return slow

        def buildTree(left: ListNode, right: ListNode) -> TreeNode:
            if left == right:
                return None
            mid = getMedian(left, right)
            root = TreeNode(mid.val)
            root.left = buildTree(left, mid)
            root.right = buildTree(mid.next, right)
            return root

        return buildTree(head, None)

[ZhangNN2018]

思路

• 快慢指针找到中间节点，中间节点即为根节点
• 去掉中间节点，左右断开
• 前半段递归找左子树, 后半段递归找右子树

复杂度

• 时间复杂度: O(N^2)；
• 空间复杂度: O(1)。

代码

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        if not head:
            return 
        slow = head
        fast = head
        p = head
        #快慢指针找到中间节点
        while fast and fast.next:
            fast = fast.next.next
            p = slow
            slow = slow.next
        #中间节点为根节点
        root = TreeNode(slow.val)
        if slow == fast:
            return root
        #去掉中间节点，左右断开
        p.next = None
        next_head = slow.next
        #前半段递归找左子树
        root.left = self.sortedListToBST(head)
        #后半段递归找右子树
        root.right = self.sortedListToBST(next_head)
        return root

[moirobinzhang]

Code:

public class Solution { public TreeNode SortedListToBST(ListNode head) { if (head == null) return null;

    return DFS(head, null);
}

public TreeNode DFS(ListNode head, ListNode tail)
{
    if (head == tail)
        return null;

    ListNode fastNode = head;
    ListNode slowNode = head;

    while(fastNode != tail && fastNode.next != tail)
    {
        fastNode = fastNode.next.next;
        slowNode = slowNode.next;
    }

    TreeNode currentRoot = new TreeNode(slowNode.val);
    currentRoot.left = DFS(head, slowNode);
    currentRoot.right = DFS(slowNode.next, tail);

    return currentRoot;
}

}

[Laurence-try]

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        if not head:
            return head
        slow = head
        fast = head
        slow_pre = None
        while fast and fast.next:
            fast = fast.next.next
            slow_pre = slow
            slow = slow.next
        if slow_pre:
            slow_pre.next = None
        node = TreeNode(slow.val)
        if fast == slow:
            return node
        node.left = self.sortedListToBST(head)
        node.right = self.sortedListToBST(slow.next)
        return node

[xj-yan]

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        num = []
        while head:
            num.append(head.val)
            head = head.next
        return self.buildBST(0, len(num) - 1, num)

    def buildBST(self, start, end, num):
        if start > end: return None
        if start == end: return TreeNode(num[start])

        mid = (start + end) // 2
        root = TreeNode(num[mid])
        root.left = self.buildBST(start, mid - 1, num)
        root.right = self.buildBST(mid + 1, end, num)
        return root

Time Complexity: O(n), Space Complexity; O(n)

[Liuxy94]

思路

没思路 参考题解 快慢指针找重点 构造子树

代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        if not head:
            return head
        pre, slow, fast = None, head, head

        while fast and fast.next:
            fast = fast.next.next
            pre = slow
            slow = slow.next
        if pre:
            pre.next = None
        node = TreeNode(slow.val)
        if slow == fast:
            return node
        node.left = self.sortedListToBST(head)
        node.right = self.sortedListToBST(slow.next)
        return node

复杂度

时间： O(nlogn)

空间： O(n)

[q815101630]

Recursive Build

我们可以递归地实现： 因为最中间的必然是一个父节点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        if not head:
            return None
        if not head.next:
            return TreeNode(head.val)

        slow = fast = head
        prev = None
        while fast and fast.next:
            fast = fast.next.next
            prev = slow
            slow = slow.next

        if prev:
            prev.next = None

        node = TreeNode(slow.val)
        node.left = self.sortedListToBST(head)
        node.right = self.sortedListToBST(slow.next)

        return node

time: T(n) = 2*T(n/2)+O(n) => O(nlogn) Space: O(logn)

[nonevsnull]

思路

• 思路与解法

• 对于linkedlist和binary tree来说，遍历都是核心
• 这里是两种遍历的综合
• 另外就是考察对于递归的思路
• 主要的思路是，先快慢指针找中间点===root，然后截断的左右两段linkedlist分别为左右子树
• 注意截断的这部分的定义，可能面试的时候紧张状态下容易出错

代码

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        return preOrder(head, null);
    }

    public TreeNode preOrder(ListNode head, ListNode end) {
        if(head == null || head == end) return null;

        ListNode fast = head;
        ListNode slow = head;

        while(fast != end && fast.next != end) {
            slow = slow.next;
            fast = fast.next;
            if(fast != null) fast = fast.next;
        }

        TreeNode root = new TreeNode(slow.val);
        root.left = preOrder(head, slow);
        root.right = preOrder(slow.next, end);

        return root;

    }
}

复杂度

time: O(NlogN) space: O(logN)

[hdyhdy]

思路：分治，中点

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedListToBST(head *ListNode) *TreeNode {
    return buildTree(head, nil)
}

func getMedian(left,right *ListNode) *ListNode{
    fast, slow := left, left
    for fast != right && fast.Next != right {
        fast = fast.Next.Next
        slow = slow.Next
    }
    return slow 
}

func buildTree (left,right *ListNode) *TreeNode{
    if left == right {
        return nil
    }
    mid := getMedian(left, right)
    root := &TreeNode{mid.Val, nil, nil}
    root.Left = buildTree(left, mid)
    root.Right = buildTree(mid.Next, right)
    return root
}

时间复杂度O(nlogn) 空间为O（logn）

[gentleman-goodman]

Day9_109_有序链表转换二叉搜索树

思路

用两个指针，一块一慢，快的每次走两步，慢的每次走一步，
这样当快指针遍历结束时，慢指针指向的也就是链表的中间位置。
这时候把中间位置的结点的值作为二叉搜索树当前结点的值
然后递归，构造出树

    class Solution {
        public TreeNode sortedListToBST(ListNode head) {
            if (head == null) {
                return null;
            }
            if (head.next == null) {
                return new TreeNode(head.val);
            }
            //快慢指针找中点
            /*pre指向中点前一个
            * slow指向中点
            * */
            ListNode fast = head, slow = head,pre=null;
            while (fast!=null&&fast.next!=null){
                fast = fast.next.next;
                pre = slow;
                slow = slow.next;

            }
            pre.next = null;

            ListNode rightList = slow.next;
                //中点
            TreeNode root = new TreeNode(slow.val);
                /*左子树*/
            root.left = sortedListToBST(head);
                /*右子树*/
            root.right = sortedListToBST(rightList);
            return root;
        }
    }

复杂度分析

[iambigchen]

思路

通过快慢节点，可以找到链表的中间节点。中间节点是当前树的根节点，再分别求出左节点和右节点即可。

关键点

代码

• 语言支持：JavaScript

JavaScript Code:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function(head) {
    if (!head) return null
    return dfs(head, null)
};

function dfs (head, tail) {
    if (head === tail) return null
    let fast = head
    let slow = head
    while(fast != tail && fast.next != tail) {
        fast = fast.next.next
        slow = slow.next
    }
    let res = new TreeNode(slow.val)
    res.left = dfs(head, slow)
    res.right = dfs(slow.next, tail)
    return res
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(logn)$
• 空间复杂度：$O(logn)$

[Aobasyp]

思路 使用快慢双指针可定位中间元素

class Solution { public TreeNode sortedListToBST(ListNode head) { if(head == null) return null; return dfs(head,null); } private TreeNode dfs(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; } TreeNode root = new TreeNode(slow.val); root.left = dfs(head, slow); root.right = dfs(slow.next, tail); return root; } }

时间复杂度：O(N) 空间复杂度：O(1)

[Myleswork]

思路

递归构建搜索树

二分实现平衡（注意边界控制）

代码

/**
 * 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* DFS(ListNode* head,ListNode* tail){
        if(head == tail) return nullptr;

        //找中间节点
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast != tail && fast->next != tail){
            slow = slow->next;
            fast = fast->next->next;
        }
        //找到中间节点，作为根节点，递归构造左右子树
        TreeNode* root = new TreeNode(slow->val);
        root->left = DFS(head,slow);        //二分注意边界
        root->right = DFS(slow->next,tail);
        return root;
    }
    TreeNode* sortedListToBST(ListNode* head) {
        if(!head) return nullptr;
        return DFS(head,nullptr);

    }
};

复杂度分析

时间复杂度：O(logn)

空间复杂度：O(logn)

[samaritan1998]

有序链表转换二叉搜索树

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        def findmid(head, tail):
            slow = head
            fast = head
            while fast != tail and fast.next!= tail :
                slow = slow.next
                fast = fast.next.next
            return slow

        def helper(head, tail):
            if  head == tail: return 
            node = findmid(head, tail)
            root = TreeNode(node.val)
            root.left = helper(head, node)
            root.right = helper(node.next, tail)
            return root

        return helper(head, None)

递归的过程

• 找到中间节点作为根节点
• 递归 中间节点的左边部分
• 递归 中间节点的右边部分

递归函数为 helper(head,tail) 返回head至tail部分的根节点

[Husky-Gong]

Node

1. Use recursion to get left and right part, until it gets the minimum case
2. minimum case: head == null || head.next == null
3. get mid and left part and right part
4. set left part as mid.left, set right as mid.right
5. return root

Code

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        // minimum case
        if (head == null){
            return null;
        }

        if (head.next == null) {
            return new TreeNode(head.val);
        }

        // get mid and left part and right part
        ListNode mid = getMid(head);
        ListNode treeRoot =  mid.next;
        ListNode rightPart = treeRoot.next;
        ListNode leftPart = head;
        mid.next = null;

        TreeNode root = new TreeNode(treeRoot.val);
        root.left = sortedListToBST(leftPart);
        root.right = sortedListToBST(rightPart);

        return root;
    }

    private ListNode getMid(ListNode head) {
        ListNode slow = new ListNode(0);
        ListNode fast = new ListNode(0);

        slow.next = head;
        fast.next = head;

        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }
}

complexity

Time Complexity: O(nlogn) -> divide Space Comlexity: O(n)

[biaohuazhou]

思路

快慢指针 找到中位数 中位数本身做根节点 中位数左边做树的左边 中位数右边做树的右边
递归寻找整颗树

代码

          class Solution {
        public TreeNode sortedListToBST(ListNode head) {
            if (head == null) {
                return null;
            }
            if (head.next == null) {
                return new TreeNode(head.val);
            }
            //找到中间位
            ListNode fast =head;
            ListNode slow =head;
            ListNode temp=null;
            //要用且 不能用或  用或就会造成空指针异常
            while (fast!=null && fast.next!=null){
                temp=slow;
                slow=slow.next;
                fast=fast.next.next;
            }
            //把链表从slow中间分开
            //也就是slow的前一个的下一个为null
            //slow的左边是树的左部  slow的右边是树的右边
            temp.next=null;
            TreeNode root =new TreeNode(slow.val);
            root.left=sortedListToBST(head);
            root.right=sortedListToBST(slow.next);
            return  root;
        }
    }

复杂度分析 时间复杂度： O(nlong(n)) n为链表的长度 空间复杂度：$O(long(n))$

[KennethAlgol]

思路

快慢指针

语言

java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }

        if (head.next == null) {
            return new TreeNode(head.val);
        }

        // 快慢指针找中心节点
        ListNode x = head, y = head, pre = null;
        while (y != null && y.next != null) {
            pre = x;
            x = x.next;
            y = y.next.next;
        }
        pre.next = null;

        // 以升序链表的中间元素作为根节点 root，递归的构建 root 的左子树与右子树。
        TreeNode root = new TreeNode(x.val);
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(x.next);
        return root;
    }
}

复杂度分析

时间复杂度 O(n) 空间复杂度 O(n)

[feifan-bai]

思路

1. fast moves two step, slow moves one step, to get the mid of the list

2. buld the tree with mid, (left, mid), (mid.next, right) 代码

   class Solution:
   def sortedListToBST(self, head: ListNode) -> TreeNode:
       def getMedian(left: ListNode, right: ListNode) -> ListNode:
           fast = slow = left
           while fast != right and fast.next != right:
               fast = fast.next.next
               slow = slow.next
           return slow
   
       def buildTree(left: ListNode, right: ListNode) -> TreeNode:
           if left == right:
               return None
           mid = getMedian(left, right)
           root = TreeNode(mid.val)
           root.left = buildTree(left, mid)
           root.right = buildTree(mid.next, right)
           return root
   
       return buildTree(head, None)

   复杂度分析

   • 时间复杂度：O(NlogN)
   • 空间复杂度：O(N)

[shamworld]

思路

快慢指针法

代码

var sortedListToBST = function(head) {
    if(!head) return null;
    function deep(left,right){
        if(left==right)return null;
        let fast = left,slow = left;
        while(fast!=right&&fast.next!=right){
            fast = fast.next.next;
            slow = slow.next;
        }
        let root = new TreeNode(slow.val);
        root.left = deep(left,slow);
        root.right = deep(slow.next,right);

        return root;
    }
    return deep(head,null);
};

复杂度分析

• 时间复杂度:O(logn);
• 空间复杂度:O(logn)

[lingli10822]

递归思想，每次只处理当前treenode。 basecase：当前节点为空或当前节点下一节点为空。 难点，需要找到当前treenode，所以需要快慢指针。

def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        if not head:
            return
        if not head.next:
            return TreeNode(head.val)
        pre = None 
        slow  = fast = head
        while fast and fast.next:
            pre = slow
            fast = fast.next.next
            slow = slow.next

        new_h = slow.next
        pre.next = None
        node = TreeNode(slow.val)
        node.left = self.sortedListToBST(head)
        node.right = self.sortedListToBST(new_h)
        return node

[LuoXingbiao]

思路

二叉搜索树的中序遍历是一个升序数组，那么构造一个二叉搜索树只需对一个升序数组进行如下操作: 1)找到当前链表的中间节点2)中间节点作为根节点3)以中间节点分隔左右两侧的链表，递归构建左右子树。

代码

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null){
            return null;
        }
        if(head.next == null){
            return new TreeNode(head.val);
        }

        ListNode pre = head;
        ListNode p = pre.next;
        ListNode q = p.next;

        while(q!=null && q.next!=null){
            pre = pre.next;
            p = p.next;
            q = q.next.next;
        }

        pre.next = null;
        TreeNode root = new TreeNode(p.val);

        root.left = sortedListToBST(head);
        root.right = sortedListToBST(p.next);

        return root;
    }
}

复杂度

时间复杂度：O(nlogn)

空间复杂度：O(logn)

[TimmmYang]

思路

DFS，每棵子树的根结点是输入的左右两边的中点。

代码

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        vals = []
        while head:
            vals.append(head.val)
            head = head.next
        def constructBST(left, right):
            if left > right:
                return
            mid = (left + right) // 2
            node = TreeNode(vals[mid])
            node.left = constructBST(left, mid-1)
            node.right = constructBST(mid+1, right)
            return node
        return constructBST(0, len(vals)-1)

复杂度

时间：O(N) N是链表长度。 空间：O(logN)

[1149004121]

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

思路

对于链表，要找到中间的结点，可以利用快慢指针，时间复杂度为O(N)，而利用数组，通过将结点存入数组中，可以通过下标实现随机存储。

代码

    var sortedListToBST = function(head) {
        let arr = [];
        let cur = head;
        while(cur){
            arr.push(cur);
            cur = cur.next;
        }
        return dfs(arr, 0, arr.length - 1);
    };

    function dfs(arr, left, right){
        if(left > right) return null;
        let mid = (left + right) >>> 1;
        let root = arr[mid];
        root.left = dfs(arr, left, mid - 1);
        root.right = dfs(arr, mid + 1, right);
        return root;
    }

复杂度分析

• 时间复杂度：O(N)，N为链表长度。
• 空间复杂度：O(N)。

[ZacheryCao]

Idea:

DFS. Every time find current linkedlinst's mid point, build its corresponding treenode. Then, seperate the linked list to two parts, the first part's tail is the node before the mid node. The second part's head is the node next to mid node. Current treenode's left side is built on the first part linked list. It's right side is built on the second part linked list. Recursively these steps until there is no lniked list or only one element in the linkedlist.

Code:

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        if not head:
            return None
        if not head.next:
            return TreeNode(head.val)
        first, second = head, head
        pre = None
        while second and second.next:
            pre = first
            first = first.next
            second = second.next.next
        second = first.next
        root = TreeNode(first.val)
        pre.next = None
        first = head
        root.left = self.sortedListToBST(first)
        root.right = self.sortedListToBST(second)
        return root

Complexity:

Time: O(NlogN) Space: O(logN)

[charlestang]

思路

如果想要二叉树平衡，则左子树和右子树的节点树尽可能一样多。

那我们每次找到中间的数字，作为根节点。然后对前面的数字递归调用，作为左子树，右子树同理。

通过快慢指针可以找到中间的节点。

代码

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        # 1. 边界条件
        if not head: return None
        if not head.next: return TreeNode(val=head.val)

        # 2. 分割
        p = slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        while p.next != slow:
            p = p.next
        p.next = None

        root = TreeNode(slow.val)
        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(slow.next)

        return root

复杂度分析

• 时间复杂度： 找到中间的节点，复杂度是O(n)，构造 BST 是 O(Log(n))，总时间复杂度是 O(n Log(n))
• 空间复杂度：O(Log(n))

[ginnydyy]

Problem

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

Note

• Recursion
  • solution 1. find mid to form the root and recursively form left sub tree and right sub tree
  • solution 2. simulate BST inorder traversal, calculate the size of list, and recursively form all the left sub trees, then root, then right sub trees.

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null){
            return null;
        }

        if(head.next == null){
            return new TreeNode(head.val);
        }

        return helper(head, null);
    }

    private TreeNode helper(ListNode head, ListNode tail){
        if(head == tail){
            return null;
        }
        // find middle node
        ListNode slow = head;
        ListNode fast = head;
        while(fast != tail && fast.next != tail){
            slow = slow.next;
            fast = fast.next.next;
        }
        // slow is the middle
        TreeNode root = new TreeNode(slow.val);
        root.left = helper(head, slow);
        root.right= helper(slow.next, tail);

        return root;

    }
}

Complexity

• T: O(nlogn). n is the number of list nodes.
• S: O(logn). Extra space is required for recursion stacks. The number of stacks is the number of the height of tree. Since the tree is balanced, the height is logn.

[tangjy149]

思路

因为本身链表已经是有序，那么只需递归寻找中间节点，便可以满足二叉搜索树的性质，寻找中间节点通过快慢指针进行。

代码

/**
 * 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) {
        if(head==nullptr) return nullptr;
        return dfs(head,nullptr);
    }

    TreeNode* dfs(ListNode* start,ListNode* end){
        if(start==end) return nullptr;
        // 快慢指针寻找中间节点
        ListNode *ptr1=start;
        ListNode *ptr2=start;
        while(ptr1!=end&&ptr1->next!=end){
            ptr1=ptr1->next->next;
            ptr2=ptr2->next;
        }
        // 生成左右子树
        TreeNode* node=new TreeNode(ptr2->val);
        node->left=dfs(start,ptr2);
        node->right=dfs(ptr2->next,end);
        return node;
    }
};

复杂度

时间复杂度：O(nlogn)

[Flower-F]

解题思路

二叉搜索树的任意一个节点，当前节点的值必然大于所有左子树节点的值，且必然小于所有右子树节点的值。获取当前链表的中点，以链表中点为根，中点左边的值都小于它，可以构造左子树；中点右边的值都大于它，可以构造右子树。获取链表的中点，可以使用快慢指针解决。

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function(head) {
    if (!head) {
        return null;
    }
    return dfs(head, null);

    function dfs(head, tail) {
        if (head === tail) {
            return null;
        }

        // 查找链表中点
        let slow, fast;
        slow = fast = head;
        while (fast !== tail && fast.next !== tail) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 此时慢指针即为中点
        const root = new TreeNode(slow.val);

        // 递归构建左子树
        root.left = dfs(head, slow);
        // 右子树
        root.right = dfs(slow.next, tail);

        return root;
    }
};

复杂度

设链表长度为 n 时间：递归树的深度为 logn，每一层的基本操作数为 n，因此总的时间复杂度为 O(nlogn) 空间：O(logn)

[phybrain]

思路

递归

代码

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        link_list = []
        while head is not None:
            val = head.val
            link_list.append(val)
            head = head.next

        def dfs(link_list,l,r):
            if l>r:
                return
            mid = int((r-l)/2)+l
            node = TreeNode(link_list[mid])
            right = dfs(link_list,mid+1,r)
            left = dfs(link_list,l,mid-1)
            node.left = left
            node.right = right
            return node
        return dfs(link_list,0,len(link_list)-1)

复杂度分析

• 时间复杂度：O(NlogN)，其中 N 为数组长度。
• 空间复杂度：O(N)

[ZJP1483469269]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        if not head:
            return head
        pre , slow , fast = None , head , head
        while fast and fast.next:
            fast = fast.next.next
            pre = slow
            slow = slow.next
        if pre:
            pre.next = None
        node = TreeNode(slow.val)
        if slow == fast:
            return node
        node.left = self.sortedListToBST(head)
        node.right = self.sortedListToBST(slow.next)
        return node

[Bochengwan]

思路

通过分治，每次从中点，left为head，right为中点后的node

代码

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        if not head:
            return None
        if not head.next:
            return TreeNode(head.val)
        prev = None
        slow = fast = head
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next
        prev.next = None

        return TreeNode(slow.val,self.sortedListToBST(head),self.sortedListToBST(slow.next))

复杂度分析

• 时间复杂度：O(NLOGN)，其中 N 为数组长度。
• 空间复杂度：O(LOGN)