LeetCode 109. 有序链表转换二叉搜索树 — Python3 实现思路中序遍历模拟二叉搜索树BST的中序遍历结果是有序的而给定的链表恰好也是有序的。因此可以模拟中序遍历的过程来构建 BST先计算链表的长度 n。递归函数 build(start, end) 表示用链表在区间 [start, end] 内的节点构建子树。取 mid (start end) // 2 作为当前子树的根节点在链表中的位置。先递归构建左子树然后取当前链表节点作为根链表指针后移再递归构建右子树。这样每个节点只访问一次且不需要额外数组。代码# Definition for singly-linked list.classListNode:def__init__(self,val0,nextNone):self.valval self.nextnext# Definition for a binary tree node.classTreeNode:def__init__(self,val0,leftNone,rightNone):self.valval self.leftleft self.rightrightclassSolution:defsortedListToBST(self,head:ListNode)-TreeNode:# 1. 计算链表长度n0curheadwhilecur:n1curcur.nextcurhead# 用于中序遍历的指针defbuild(start:int,end:int)-TreeNode:nonlocalcurifstartend:returnNonemid(startend)//2# 先构建左子树leftbuild(start,mid-1)# 当前链表节点即为根节点nodeTreeNode(cur.val)curcur.nextnode.leftleft# 再构建右子树node.rightbuild(mid1,end)returnnodereturnbuild(0,n-1)复杂度分析· 时间复杂度O(n)每个节点被访问一次。· 空间复杂度O(log n)递归栈深度为树的高度由于构建的是平衡 BST高度为 O(log n)。另一种简单解法转数组如果不想模拟中序也可以先把链表转为数组然后递归取中点建树classSolution:defsortedListToBST(self,head:ListNode)-TreeNode:vals[]whilehead:vals.append(head.val)headhead.nextdefbuild(l:int,r:int)-TreeNode:iflr:returnNonemid(lr)//2nodeTreeNode(vals[mid])node.leftbuild(l,mid-1)node.rightbuild(mid1,r)returnnodereturnbuild(0,len(vals)-1)· 时间复杂度O(n)· 空间复杂度O(n)额外数组模拟中序的写法空间更优推荐使用。