深度优先搜索、快慢指针:力扣109. 有序链表转换二叉搜索树
程序员文章站
2022-05-06 21:37:17
...
1、题目描述:
2、题解:
推荐和下面的两道题一起做:
深度优先搜索:力扣108. 将有序数组转换为二叉搜索树
二叉搜索树:力扣1382. 将二叉搜索树变平衡
**方法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)
上一篇: Spring事务的传播行为
下一篇: Spring事务的传播行为