6.数据结构---树（链表、数组、二叉树转换）

一、有序数组转换为二叉搜索树

思路：递归 时间复杂度O(N) 空间复杂度O(1) 

nums为空，return None nums非空，nums[n/2]为中间元素，根结点，nums[:mid]为左子树， nums[mid+1:]为右子树

class Solution:
    def sortedArrayToBST(self, nums):
        if len(nums) == 0:
            return None

        mid = len(nums) // 2
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[0:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])

        return root

二、有序链表转换为二叉搜索树

思路1：利用快慢指针的思想寻找链表中点，将其分为两个部分，再继续找左右两个新链表的中点。 当慢指针不与出发点重合时，说明这个子链的长度<3,此时只要把子链的右边节点（如果有的话） 作为左节点的右子树即可 时间复杂度O(N) 空间复杂度O(1)

class Solution:
    def sortedListToBST(self, head):
        def getMid(node):
            if not node:
                return

            slow = node
            fast = node
            pre_slow = None

            while fast.next and fast.next.next:
                fast = fast.next.next
                pre_slow = slow
                slow = slow.next

            if slow == node:#中心点=head,没有左子树
                return None,slow #返回左,中心点
            else: #中心点!=None
                pre_slow.next = None#左子树到slow前一个节点结束
                return node,slow

        left_head,mid_node = getMid(head)
        root = TreeNode(mid_node.val) #中心点
        right_head = mid_node.next

        root.left = self.sortedListToBST(left_head)
        root.right = self.sortedListToBST(right_head)
        return root