[Leetcode][python]Convert Sorted List to Binary Search Tree
[Leetcode][python]Convert Sorted List to Binary Search Tree
蛮三刀酱
发布于 2019-03-26 17:11:09
发布于 2019-03-26 17:11:09
题目大意
将一个升序链表转为有序二叉树 和上一题的不同仅仅是将数组换成了链表
解题思路
- 首先想到的是将链表存入数组，然后和上一题相同。
- 网上思路是用快慢指针，慢指针每次走一格,快指针每次走两格 具体来说，也是找中间指针,快指针走到最后，慢指针走到中间。然后将中间数作为左边递归的最后一个数，右边则是中间开始到最后。递归下去。
代码
转为数组（街上一题）
# 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)第一种方法比第二种在运算速度上要快
总结
这题直接从上一题自己的代码改的，要说有什么总结直接看上一题就好了。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年07月27日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录