首页 > 代码库 > [leetcode]Convert Sorted List to Binary Search Tree @ Python

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

2024-07-04 02:50:23   227人阅读

原题地址：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)

 


联系
我们