python实现leetcode之109. 有序链表转换二叉搜索

解题思路

先计算出链表的长度
然后寻找root节点切分左右
然后递归处理左右

109. 有序链表转换二叉搜索树

代码

# 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
        """
        length = len_of_chain(head)
        return chain2tree(head, length)


def chain2tree(start, limit):
    if limit <= 0: return None
    left_len = limit / 2
    right_len = limit-left_len-1
    left = chain2tree(start, left_len)
    while left_len:
        start = start.next
        left_len -= 1
    root = TreeNode(start.val)
    root.left = left
    root.right = chain2tree(start.next, right_len)
    return root

def len_of_chain(head):
    if not head: return 0
    return len_of_chain(head.next) + 1