深度优先搜索、快慢指针（有序链表转换二叉搜索树）

1、题目描述：

2、题解： 

**方法1：**先把有序链表转化为有序数组，然后按照深度优先搜索：力扣108. 将有序数组转换为二叉搜索树的思路去做。

# Definition for singly-linked list. # class ListNode: #     def __init__(self, x): #         self.val = x #         self.next = None # Definition for a binary tree node. # class TreeNode: #     def __init__(self, x): #         self.val = x #         self.left = None #         self.right = None class Solution: def sortedListToBST(self, head: ListNode) -> TreeNode: #将有序数组变换成平衡的二叉搜索树 def inorder(nums): if not nums: return mid_index = len(nums) // 2 mid = nums[mid_index] root = TreeNode(nums[mid_index]) root.left = inorder(nums[:mid_index]) root.right = inorder(nums[mid_index+1:]) return root #将有序链表转化为有序数组 if not head: return None nums = [] while head: nums.append(head.val) head = head.next return inorder(nums)

方法2：快慢指针找中间值，然后处理左右子树
我们设置快慢指针，当快指针走到末尾，那么慢指针就指向中间，然后创建结点，分别递归处理左、右子树。
注意快慢指针的一些细节(温馨提示：在代码中，我们找的是第二个中间结点）

# Definition for singly-linked list. # class ListNode: #     def __init__(self, x): #         self.val = x #         self.next = None # Definition for a binary tree node. # class TreeNode: #     def __init__(self, x): #         self.val = x #         self.left = None #         self.right = None class Solution: def sortedListToBST(self, head: ListNode) -> TreeNode: # 快慢指针找中间值 if not head: return pre,slow,fast = None,head,head while fast and fast.next: pre = slow
            slow = slow.next fast = fast.next.next #这个时候pre是中间值的前一个节点，slow是中间值 temp = slow.next root = TreeNode(slow.val) if pre : pre.next = None #这样才会把前面的一部分和中间值分开 root.left = self.sortedListToBST(head) root.right = self.sortedListToBST(temp) return root

当然也可以把快慢指针进行封装：
代码如下：

class Solution: def sortedListToBST(self, head: ListNode) -> TreeNode: if not head: return mid = self.findMid(head) root = TreeNode(mid.val) if head == mid: #也就是说剪枝，此时中间指针就是本身，直接返回 return root

        root.left = self.sortedListToBST(head) root.right = self.sortedListToBST(mid.next) return root # 快慢指针找中间值 def findMid(self,head): pre, slow, fast = None, head, head while fast and fast.next: pre = slow
            slow = slow.next fast = fast.next.next # 这个时候pre是中间值的前一个节点，slow是中间值 if pre: pre.next = None return slow

3、复杂度分析：

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

方法2：
时间复杂度：O(N logN)
空间复杂度：O(logN)

本文地址：https://blog.csdn.net/weixin_42042056/article/details/107106790