LeetCode 109. Convert Sorted List to Binary Search Tree.jpg
LeetCode 109. Convert Sorted List to Binary Search Tree
Description
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
Given the sorted linked list: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/ \
-3 9
/ /
-10 5
描述
给定一个链表，其中元素按升序排序，将其转换为高度平衡的BST。
对于这个问题，高度平衡的二叉树被定义为:二叉树中每个节点的两个子树的深度从不相差超过1。
例：
给定排序数组：[ - 10，-3,0,5,9]，
一个可能的答案是：[0，-3,9，-10，null，5]，它代表以下高度平衡的BST：
0
/ \
-3 9
/ /
-10 5
思路
- 此题目与108题类似，只不过给定的原始数据由108题的数组，变成了链表，链表的元素不支持随机访问，导致取中间值不能够通过索引来取得.
- 这里着重说明以下取链表中间值的操作：我们用两个指针slow和fast，slow指针每次向后走一个位置，fast指针每次向后走两个位置，当fast到达末尾时，slow就到达了中间位置.
- 注意结束条件：由于fast指针是被允许走到end位置的，于是就不能用fast.next.next == end 来作为结束条件.由于fast指针每次能够向后走两步，于是fast.enxt == end 时就应该结束循环，fast == end 时 也应该结束循环.
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2018-12-30 13:57:09
# @Last Modified by: 何睿
# @Last Modified time: 2018-12-30 15:47:35
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):
"""
:type head: ListNode
:rtype: TreeNode
"""
if not head:
return None
return self.recursion(head, None)
# 链表从start开始，到end结束，左闭右开，[start,end),包括start节点，不包括end节点
def recursion(self, start, end):
# 取中间值作为当前根节点
middle = self.serachmid(start, end)
# 递归结束条件，当left大于right时,返回空节点
if not middle:
return None
# 声明根节点
root = TreeNode(middle.val)
# 生成左子树
leftree = self.recursion(start, middle)
# 生成右子树
rightree = self.recursion(middle.next, end)
root.left = leftree
root.right = rightree
# 返回根节点
return root
# 寻找中间值
def serachmid(self, start, end):
# 搜索一个链表的中间值
if start == end:
return None
if start.next == end:
return start
slow, fast = start, start.next
# 因为fast每次需要向后走两步，而fast.next.next == end时，fast是被允许走到end的
# 于是就不能用fast.next.enxt == end 作为结条件，结束条件为fast.next != end and fast !=end:
while fast and fast.next and fast.next != end and fast !=end:
slow = slow.next
fast = fast.next.next
return slow
