【Day 9 】2023-06-18 - 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

[Fuku-L]

代码

/**
 * 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) {
        // 递归+快慢指针
        return buildTree(head, null);
    }

    public TreeNode buildTree(ListNode left, ListNode right){
        if(left == right){
            return null;
        }
        ListNode mid = getMedian(left, right);
        TreeNode root = new TreeNode(mid.val);
        root.left = buildTree(left, mid);
        root.right = buildTree(mid.next, right);
        return root;
    }

    public ListNode getMedian(ListNode left, ListNode right){
        ListNode fast = left;
        ListNode slow = left;
        while(fast != right && fast.next != right){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

[Alexno1no2]

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

        return newhead

[bi9potato]

Approach

Fast n slow pointers to get the middle node, then use BFS recursively.

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) {

        return dfs(head, null);

    }

    private TreeNode dfs(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 = dfs(head, slow);
        root.right = dfs(slow.next, tail);

        return root;

    }
}

Complexity Analysis

• Time $\mathcal{O}(N\log{N})$
• Spce $\mathcal{O}(N)$

[zhaoygcq]

思路

确定如何正确的定位中间节点： 快慢指针是一种办法，如果快指针一次走两步、慢指针一次走一步， 那快指针指向链表末尾时，慢指针正好在中间.

代码

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
function sortedListToBST (head) {
    if(!head) return head;
    let slow = fast = head;
    let slowPrev = null;
    while(fast && fast.next) {
        slowPrev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }

    let root = new TreeNode(slow.val);
    if(slowPrev) {
        slowPrev.next = null;
        root.left = sortedListToBST(head);
    }
    root.right = sortedListToBST(slow.next);
    return root;
};

复杂度分析

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

[acy925]

代码

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

[wzbwzt]

/* 思路： 快慢指针 前提：链表已经升序排序 根据高度平衡的二叉树原则，可以先选取中间节点作为根节点,左边的都为左节点，右边的都为右节点 对左右子链表再找中间节点,以此重复； 通过快慢指针找到中间节点

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

*/

// 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 {
    if head == nil {
        return nil
    }
    if head.Next == nil {
        return &TreeNode{Val: head.Val}
    }
    if head.Next.Next == nil {
        return &TreeNode{Val: head.Next.Val, Left: &TreeNode{Val: head.Val}}
    }

    var pre *ListNode
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        pre = slow
        slow = slow.Next
        fast = fast.Next.Next
    }
    root := &TreeNode{Val: slow.Val}
    root.Right = sortedListToBST(slow.Next)

    pre.Next = nil
    root.Left = sortedListToBST(head)

    return root

}

[GuitarYs]

# 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 None
        if not head.next:
            return TreeNode(head.val)
        # 寻找链表中点
        slow, fast = head, head.next.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        # 将链表断开，分别构建左子树和右子树
        mid = slow.next
        slow.next = None
        root = TreeNode(mid.val)
        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(mid.next)
        return root

# 示例
head = ListNode(-10)
head.next = ListNode(-3)
head.next.next = ListNode(0)
head.next.next.next = ListNode(5)
head.next.next.next.next = ListNode(9)

solution = Solution()
root = solution.sortedListToBST(head)

def printTree(root):
    if not root:
        return
    print(root.val)
    printTree(root.left)
    printTree(root.right)

printTree(root)

[catkathy]

思路

快慢指针

Code

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

        dummy = ListNode(0)
        dummy.next = head
        slow, fast, prev = head, head, dummy

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

        new_head = slow.next
        prev.next = None  

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

        return root

复杂度分析：

• Time: O(n)
• Space: O(n)

[hengistchan]

/**
 * 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) {
        // 递归+快慢指针
        return buildTree(head, null);
    }

    public TreeNode buildTree(ListNode left, ListNode right){
        if(left == right){
            return null;
        }
        ListNode mid = getMedian(left, right);
        TreeNode root = new TreeNode(mid.val);
        root.left = buildTree(left, mid);
        root.right = buildTree(mid.next, right);
        return root;
    }

    public ListNode getMedian(ListNode left, ListNode right){
        ListNode fast = left;
        ListNode slow = left;
        while(fast != right && fast.next != right){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

[Diana21170648]

思路

用双指针解题

代码

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(nlogn)，其中 n为每一层的操作数，logn为二叉树的深度。
• 空间复杂度：O(logn)，logn为二叉树的深度

[snmyj]

class Solution {

    public TreeNode sortedListToBST(ListNode head) {
        return buildTree(head,null);
    }

    public TreeNode buildTree(ListNode left,ListNode right){
        if(left == right){
            return null;
        }
        ListNode mid = getMid(left,right);
        TreeNode root = new TreeNode();
        root.val = mid.val;
        root.left = buildTree(left,mid);
        root.right = buildTree(mid.next,right);
        return root;
    }

    public ListNode getMid(ListNode left,ListNode right){
        ListNode slow = left;
        ListNode fast = left;
        while(fast != right && fast.next != right){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

}

[SoSo1105]

思路

快慢指针。使用快慢指针找到链表的中间节点，即为二叉搜索树的根节点，然后递归链表左半部分和右半部分

代码

# 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 head is None:
            return None
        if head.next is None:
            return TreeNode(head.val)
        slow = ListNode(-1)
        slow.next = head
        fast = head
        while fast is not None:
            last = slow
            slow = slow.next
            fast = fast.next.next if fast.next is not None else None
        last.next = None
        right = slow.next
        slow.next = None
        root = TreeNode(slow.val)
        if slow is not head:
            root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(right)
        return root 

复杂度分析

• 时间复杂度：O(NLogN)
• 空间复杂度：O(LogN)

[zhangyu1131]

/**
 * 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)
        {
            return nullptr;
        }

        ListNode* slow = head;
        ListNode* fast = head->next;
        ListNode* pre = nullptr;
        while (fast)
        {
            fast = fast->next;
            if (fast)
            {
                fast = fast->next;
            }
            pre = slow;
            slow = slow->next;
        }
        // 找到slow为根节点
        TreeNode* root = new TreeNode(slow->val);
        if (pre)
        {
            pre->next = nullptr;
        }
        ListNode* next = slow->next;
        slow->next = nullptr;

        if (slow != head) //如果就是唯一的节点，那就没有左子树了
        {
            root->left = sortedListToBST(head);
        }
        root->right = sortedListToBST(next);

        return root;
    }
};

[guangsizhongbin]

题目地址(109. 有序链表转换二叉搜索树)

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

题目描述

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

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

 

示例 1:

输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。

示例 2:

输入: head = []
输出: []

 

提示:

head 中的节点数在[0, 2 * 104] 范围内
-105 <= Node.val <= 105

前置知识

公司

• 暂无

思路

关键点

代码

• 语言支持：Go

Go Code:

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
}

复杂度分析

令 n 为数组长度。

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

[Hughlin07]

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;
}

}

[61hhh]

代码

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

        // 找到链表的中间节点
        ListNode slow = head, fast = head.next.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 以中间节点的值创建根节点
        TreeNode root = new TreeNode(slow.next.val);

        // 递归地构建左子树和右子树
        ListNode rightHead = slow.next.next;
        slow.next = null;
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(rightHead);

        return root;
    }
}

复杂度分析

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

[Beanza]

代码

/**

• 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) { // 递归+快慢指针 return buildTree(head, null); }

  public TreeNode buildTree(ListNode left, ListNode right){ if(left == right){ return null; } ListNode mid = getMedian(left, right); TreeNode root = new TreeNode(mid.val); root.left = buildTree(left, mid); root.right = buildTree(mid.next, right); return root; }

  public ListNode getMedian(ListNode left, ListNode right){ ListNode fast = left; ListNode slow = left; while(fast != right && fast.next != right){ fast = fast.next.next; slow = slow.next; } return slow; } }

[C2tr]

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

    // 找到链表的中间节点
    ListNode slow = head, fast = head.next.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    TreeNode root = new TreeNode(slow.next.val);

    ListNode rightHead = slow.next.next;
    slow.next = null;
    root.left = sortedListToBST(head);
    root.right = sortedListToBST(rightHead);

    return root;
}

}

[yetfan]

代码

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)

[kingxiaozhe]

// 定义链表节点
class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

// 定义二叉树节点
class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

// 将有序链表转换为高度平衡的二叉搜索树
function sortedListToBST(head) {
  if (!head) return null;

  const nums = [];
  let curr = head;

  // 将链表中的值存储到数组中
  while (curr) {
    nums.push(curr.val);
    curr = curr.next;
  }

  // 构建二叉搜索树
  function buildBST(left, right) {
    if (left > right) return null;

    const mid = Math.floor((left + right) / 2);
    const root = new TreeNode(nums[mid]);

    root.left = buildBST(left, mid - 1);
    root.right = buildBST(mid + 1, right);

    return root;
  }

  return buildBST(0, nums.length - 1);
}

// 创建链表 [-10, -3, 0, 5, 9]
const head = new ListNode(-10);
head.next = new ListNode(-3);
head.next.next = new ListNode(0);
head.next.next.next = new ListNode(5);
head.next.next.next.next = new ListNode(9);

// 转换为二叉搜索树
const root = sortedListToBST(head);

// 打印二叉搜索树
function printBinaryTree(root) {
  if (!root) return;
  console.log(root.val);
  printBinaryTree(root.left);
  printBinaryTree(root.right);
}

printBinaryTree(root);

[SunStrongChina]

思路

不断地找中值作为根节点，左右节点分段寻找

def constructTree(head,tail):
    if head == tail:
        return None
    fast = head
    slow = head
    while fast != tail and fast.next != tail:
        fast = fast.next.next
        slow = slow.next
    root = TreeNode(slow.val)
    root.left = constructTree(head,slow)
    root.right = constructTree(slow.next,tail)
    return root
class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        if head is None:
            return head
        return constructTree(head,None)

时间复杂度O(nlogn)

空间复杂度O(n)

[joemonkeylee]

function sortedListToBST(head: ListNode | null): TreeNode | null {
  if (head === null) return null;

  let slow: ListNode | null = head;
  let fast: ListNode | null = head;
  let prev: ListNode | null = null;

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

  const middle = slow!;
  const node = new TreeNode(middle.val);
  if (head === middle) return node;

  prev!.next = null;

  node.left = sortedListToBST(head);
  node.right = sortedListToBST(middle.next);

  return node;
}

[Sencc]

代码：

class Solution:

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

    def build_bst(left, right):
        if left > right:
            return None
        mid = (left + right) // 2
        root = TreeNode(nums[mid])
        root.left = build_bst(left, mid - 1)
        root.right = build_bst(mid + 1, right)
        return root

    return build_bst(0, len(nums) - 1)

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

[RanDong22]

var sortedListToBST = function(head) {
    let child = head;
    const arr = [];
    while(child) {
        arr.push(child.val);
        child = child.next;
    }
    function buildTree(arr, left, right) {
        if(left > right) return null;
        if(left === right) return new TreeNode(arr[left]);
        else if (right - left === 1) {
            let r = new TreeNode(arr[right]);
            r.left = new TreeNode(arr[left]);
            return r;
        }
        let mid = (left + right + 1) >> 1;
        let root = new TreeNode(arr[mid])
        root.left = buildTree(arr, left, mid - 1);
        root.right = buildTree(arr, mid + 1, right);
        return root;
    }
    return buildTree(arr, 0, arr.length - 1);
};

[yzhyzhyzh123]

代码

[yzhyzhyzh123]

代码

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        List<Integer> nums = new ArrayList<>();
        while(head != null){
            nums.add(head.val);
            head = head.next;
        }
        TreeNode root = toBST(nums, 0, nums.size() - 1);
        return root;
    }
    public TreeNode toBST(List<Integer> nums, int be, int ed){
        if(be > ed) return null;
        TreeNode root = new TreeNode(nums.get(be + (ed - be) / 2));
        root.left = toBST(nums, be, be + (ed - be) / 2 - 1);
        root.right = toBST(nums, be + (ed - be) / 2 + 1, ed);
        return root;
    }
}

复杂度分析

时间复杂度O（n）

[dorian-byte]

思路：

这段代码实现了将有序链表转换为二叉搜索树的功能。可以使用递归的方式来解决这个问题。

我们可以使用快慢指针找到链表的中间节点，然后以中间节点作为根节点构建二叉搜索树。中间节点的左边将构成左子树，中间节点的右边将构成右子树。递归地处理左右子链表，将它们分别转换为左右子树。

具体步骤如下：

处理基本情况：如果链表为空，返回 None。如果链表只有一个节点，将该节点作为根节点返回。 使用快慢指针找到链表的中间节点。初始时，将快指针和慢指针都指向链表的头节点。 快指针每次向前移动两步，慢指针每次向前移动一步，直到快指针到达链表末尾或者下一个节点为空。 此时，慢指针指向链表的中间节点。 将中间节点作为根节点创建一个新的二叉树节点。 将中间节点的左侧链表作为左子链表，递归地调用 sortedListToBST 函数构建左子树，并将返回的根节点赋值给根节点的左指针。 将中间节点的右侧链表作为右子链表，递归地调用 sortedListToBST 函数构建右子树，并将返回的根节点赋值给根节点的右指针。 返回根节点。

代码：

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

        # Find the middle element for root
        slow, fast = head, head.next.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # Cut off the list from the middle
        mid = slow.next
        slow.next = None

        # Create a new tree node with mid element
        node = TreeNode(mid.val)
        node.left = self.sortedListToBST(head)
        node.right = self.sortedListToBST(mid.next)

        return node

复杂度分析：

时间复杂度：O(nlogn)，其中 n 是链表的长度。在每次递归调用中，都需要遍历链表找到中间节点，共需 logn 次。每次找到中间节点后，需要进行链表切割操作，时间复杂度为 O(1)。因此，总时间复杂度为 O(nlogn)。

空间复杂度：O(logn)。

(以上内容由ChatGPT生成。我通过对比ChatGPT的答案来修改自己写的代码，然后再自己打一遍。)

[RestlessBreeze]

code

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head, ListNode* end) {
        if (head == end)
            return nullptr;
        if (head->next == end)
        {
            TreeNode* temp = new TreeNode(head->val);
            return temp;
        }
        ListNode* f = head;
        ListNode* s = head;
        while (f != end && f->next != end)
        {
            f = f->next->next;
            s = s->next;
        }
        TreeNode* temp = new TreeNode(s->val);
        temp->left = sortedListToBST(head, s);
        temp->right = sortedListToBST(s->next, end);
        return temp;
    }

    TreeNode* sortedListToBST(ListNode* head)
    {
        return sortedListToBST(head, nullptr);
    }
};

[mo660]

思路

使用快慢指针，遍历出链表的中点，然后使用递归，遍历出每一段的中点

代码

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

[954545647]

var sortedListToBST = function (head) {
  if (!head) return head;
  let temp = head;
  const arr = []
  while (temp) {
    arr.push(temp.val);
    temp = temp.next;
  }

  function bfs(start, end) {
    if (start > end) return null;
    const middle = Math.floor((start + end) / 2);
    const val = arr[middle];
    const root = new TreeNode(val);
    root.left = bfs(start, middle - 1);
    root.right = bfs(middle + 1, end);
    return root
  }

  return bfs(0, arr.length - 1)
};

[Moin-Jer]

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;
        ListNode 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;
    }
}