给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表: [-10, -3, 0, 5, 9]
,
一个可能的答案是:[0, -3, 9, -10, null, 5]
, 它可以表示下面这个高度平衡二叉搜索树:
0
/ \
-3 9
/ /
-10 5
每次找到中间位置的节点作为当前的根结点,然后将左边半段作为左子树,右边半段作为右子树,递归地构建树。
由于链表有序,可保证二叉树是搜索树。
# 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 sortedListToBST(self, head):
"""
:type head: ListNode
:rtype: TreeNode
"""
if not head:
return None
# 先找到中间的点,作为树的头结点
root = self.getMidNode(head, None)
TreeRoot = TreeNode(root.val)
if head:
TreeRoot.left = self.buildTree(head, root)
if root.next:
TreeRoot.right = self.buildTree(root.next, None)
return TreeRoot
def buildTree(self, pHead, pEnd):
# 如果开头=结尾,说明段内没有节点,返回空
if pHead == pEnd:
return None
# 如果只有当前一个节点
if not pHead.next:
return TreeNode(pHead.val)
mid = self.getMidNode(pHead, pEnd)
midNode = TreeNode(mid.val)
if mid:
midNode.left = self.buildTree(pHead, mid)
if mid.next:
midNode.right = self.buildTree(mid.next, pEnd)
return midNode
def getMidNode(self, head, tail):
p1 = head
p2 = head
while p2 != tail and p2.next != tail:
p1 = p1. next
p2 = p2.next.next
return p1