给出一个已经排序的单链表，依此构建BST，DFS，注意每次搜索某一段的中间节点之后，要把next节点设为None
1 #109
2 #Runtime: 109 ms (Beats 82.72%)
3 #Memory: 19.8 MB (Beats 94.44%)
4
5 # Definition for singly-linked list.
6 # class ListNode(object):
7 # def __init__(self, val=0, next=None):
8 # self.val = val
9 # self.next = next
10 # Definition for a binary tree node.
11 # class TreeNode(object):
12 # def __init__(self, val=0, left=None, right=None):
13 # self.val = val
14 # self.left = left
15 # self.right = right
16 class Solution(object):
17 def get_middle_element(self, head):
18 d_node = head
19 s_node = head
20 while d_node and d_node.next:
21 d_node = d_node.next.next
22 pre = s_node
23 s_node = s_node.next
24 if pre:
25 pre.next = None
26 return s_node
27
28
29 def sortedListToBST(self, head):
30 """
31 :type head: Optional[ListNode]
32 :rtype: Optional[TreeNode]
33 """
34 if not head:
35 return None
36 if not head.next:
37 return TreeNode(head.val)
38 mid = self.get_middle_element(head)
39 root = TreeNode(mid.val)
40 root.right = self.sortedListToBST(mid.next)
41 mid.next = None
42 root.left = self.sortedListToBST(head)
43 return root