[leetcode]Convert Sorted List to Binary Search Tree @ Python

原题地址：http://oj.leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

题意：将一条排序好的链表转换为二叉查找树，二叉查找树需要平衡。

解题思路：两个思路：一，可以使用快慢指针来找到中间的那个节点，然后将这个节点作为树根，并分别递归这个节点左右两边的链表产生左右子树，这样的好处是不需要使用额外的空间，坏处是代码不够整洁。二，将排序好的链表的每个节点的值存入一个数组中，这样就和http://www.cnblogs.com/zuoyuan/p/3722103.html这道题一样了，代码也比较整洁。

代码：

# 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 sortedArrayToBST(self, array):

        length = len(array)

        if length==0: return None

        if length==1: return TreeNode(array[0])

        root = TreeNode(array[length/2])

        root.left = self.sortedArrayToBST(array[:length/2])

        root.right = self.sortedArrayToBST(array[length/2+1:])

        return root

    def sortedListToBST(self, head):

        array = []

        p = head

        while p:

            array.append(p.val)

            p = p.next

        return self.sortedArrayToBST(array)

巴特西

[leetcode]Convert Sorted List to Binary Search Tree @ Python

最新文章

热门文章