[Leetcode][python]Convert Sorted List to Binary Search Tree

叁歲伎倆 2022-06-11 01:17 131阅读 0赞

## 题目大意 ##

将一个升序链表转为有序二叉树  
和[上一题][Link 1]的不同仅仅是将数组换成了链表

## 解题思路 ##

1.  首先想到的是将链表存入数组，然后和上一题相同。
2.  网上思路是用快慢指针，慢指针每次走一格,快指针每次走两格  
    具体来说，也是找中间指针,快指针走到最后，慢指针走到中间。然后将中间数作为左边递归的最后一个数，右边则是中间开始到最后。递归下去。

## 代码 ##

### 转为数组（街上一题） ###

# Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def sortedArrayToBST(self, nums):
            """
            :type nums: List[int]
            :rtype: TreeNode
            """
            if len(nums) == 0:
                return None
            if len(nums) == 1:
                return TreeNode(nums[0])
            if len(nums)%2 == 1:
                tree = TreeNode(nums[len(nums)/2])
                tree.left = self.sortedArrayToBST(nums[:(len(nums)/2)])
                tree.right = self.sortedArrayToBST(nums[-(len(nums)/2):])
            else:
                tree = TreeNode(nums[len(nums)/2-1])
                tree.left = self.sortedArrayToBST(nums[:(len(nums)/2)-1])
                tree.right = self.sortedArrayToBST(nums[-(len(nums)/2):])
            return tree
        def sortedListToBST(self, head):
            """
            :type head: ListNode
            :rtype: TreeNode
            """
            array = []
            if head:
                while head:
                    array.append(head.val)
                    head = head.next
                return self.sortedArrayToBST(array)
            return []

### 快慢指针 ###

# Definition for a  binary tree node
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    #
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        # @param head, a list node
        # @return a tree node
        def convert(self,head,tail):
            if head==tail:
                return None
            if head.next==tail:
                return TreeNode(head.val)
            mid=head
            fast=head
            while fast!=tail and fast.next!=tail:
                fast=fast.next.next
                mid=mid.next
            node=TreeNode(mid.val)
            node.left=self.convert(head,mid)
            node.right=self.convert(mid.next,tail)
            return node
        def sortedListToBST(self, head):
            return self.convert(head,None)

第一种方法比第二种在运算速度上要快

## 总结 ##

这题直接从上一题自己的代码改的，要说有什么总结直接看上一题就好了。

[Link 1]: http://blog.csdn.net/qqxx6661/article/details/76100836