<s> """<STR_LIT>""" <EOL> __author__ = '<STR_LIT>' <EOL> class TreeNode : <EOL> def __init__ ( self , x ) : <EOL> self . val = x <EOL> self . left = None <EOL> self . right = None <EOL> class ListNode : <EOL> def __init__ ( self , x ) : <EOL> self . val = x <EOL> self . next = None <EOL> class Solution : <EOL> def __init__ ( self ) : <EOL> self . current_node = None <EOL> def sortedListToBST ( self , head ) : <EOL> """<STR_LIT>""" <EOL> if not head : <EOL> return head <EOL> self . current_node = head <EOL> length = self . getLength ( head ) <EOL> return self . sortedListToBST_dfs ( <NUM_LIT:0> , length - <NUM_LIT:1> ) <EOL> def sortedListToBST_dfs ( self , start , end ) : <EOL> if start > end : <EOL> return <EOL> mid = ( start + end ) / <NUM_LIT:2> <EOL> left_subtree = self . sortedListToBST_dfs ( start , mid - <NUM_LIT:1> ) <EOL> root = TreeNode ( self . current_node . val ) <EOL> self . current_node = self . current_node . next <EOL> right_subtree = self . sortedListToBST_dfs ( mid + <NUM_LIT:1> , end ) <EOL> root . left = left_subtree <EOL> root . right = right_subtree <EOL> return root <EOL> def getLength ( self , head ) : <EOL> count = <NUM_LIT:0> <EOL> while head : <EOL> head = head . next <EOL> count += <NUM_LIT:1> <EOL> return count </s>
