首页 > 代码库 > leetcode 【 Convert Sorted List to Binary Search Tree 】python 实现
leetcode 【 Convert Sorted List to Binary Search Tree 】python 实现
题目：
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
代码：oj测试通过 Runtime: 178 ms
1 # Definition for a binary tree node 2 # class TreeNode: 3 # def __init__(self, x): 4 # self.val = x 5 # self.left = None 6 # self.right = None 7 # 8 # Definition for singly-linked list. 9 # class ListNode:10 # def __init__(self, x):11 # self.val = x12 # self.next = None13 14 class Solution:15 # @param head, a list node16 # @return a tree node17 def sortedListToBST(self, head):18 # special case frist19 if head is None:20 return None21 if head.next is None:22 return TreeNode(head.val)23 # slow point & fast point trick to divide the list 24 slow = ListNode(0)25 fast = ListNode(0)26 slow.next = head27 fast.next = head28 while fast.next is not None and fast.next.next is not None:29 slow = slow.next30 fast = fast.next.next31 left = head32 right = slow.next.next33 root = TreeNode(slow.next.val)34 slow.next.next = None # cut the connection bewteen right child tree and root TreeNode35 slow.next = None # cut the connection between left child tree and root TreeNode36 root.left = self.sortedListToBST(left)37 root.right = self.sortedListToBST(right)38 return root
思路：
binary search tree 是什么先搞清楚
由于是有序链表，所以可以采用递归的思路，自顶向下建树。
1. 每次将链表的中间节点提出来；链表中间节点之前的部分作为左子树继续递归；链表中间节点之后的部分作为右子树继续递归。
2. 停止递归调用的条件是传递过去的head为空(某叶子节点为空)或者只有一个ListNode（到某叶子节点了）。
找链表中间节点的时候利用快慢指针的技巧：注意，因为前面的special case已经将传进来为空链表和长度为1的链表都处理了，所以快慢指针的时候需要判断一下从最短长度为2的链表的处理逻辑。之前的代码在while循环中只判断了fast.next.next is not None就忽略了链表长度为2的case，因此补上了一个fast.next is not None的case，修改过一次就AC了。
网上还有一种思路，只需要走一次链表就可以完成转换，利用的是自底向上建树。下面这个日志中有说明，留着以后去看看。
http://blog.csdn.net/nandawys/article/details/9125233
leetcode 【 Convert Sorted List to Binary Search Tree 】python 实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。