欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

深度优先搜索、快慢指针:力扣109. 有序链表转换二叉搜索树

程序员文章站 2022-05-06 21:37:17
...

1、题目描述:

深度优先搜索、快慢指针:力扣109. 有序链表转换二叉搜索树

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)

相关标签: LeetCode