109. 有序链表转换二叉搜索树 好

109. 有序链表转换二叉搜索树

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

方法一：数组存储+中序遍历

时间复杂度：O(n)，用 O(1) 时间找到数组中间元素，总体复杂度相当于只遍历了一遍数组。
空间复杂度：O(n)。

//1，转换为数组+中序遍历
func sortedListToBST(head *ListNode) *TreeNode {
    arr := []int{}
    for head != nil {
        arr = append(arr, head.Val)     //1，链表的值，全部转化为数组
        head = head.Next
    }
    return buildBST(arr, 0, len(arr)-1)     //2，返回递归函数，参数为起止二叉树节点，0，len
}
func buildBST(arr []int, start, end int) *TreeNode {
    if start > end {
        return nil          //3,递归结束条件
    }
    mid := (start + end) >> 1   //4,取中间值，防止溢出
    //mid := start + (end -start)/2
    root := &TreeNode{Val: arr[mid]}    //5，中序遍历
    root.Left = buildBST(arr, start, mid-1)
    root.Right = buildBST(arr, mid +1 , end)
    return root
}

方法二：快慢指针+递归

时间复杂度：根据递归式可知，T(n) = 2 * T（n / 2 ) + n，O(nlog(n))。==On找中点，时间变长了。
空间复杂度：O(log(n))。==空间变小了

//递归+快慢指针
func sortedListToBST(head *ListNode) *TreeNode {
    if head == nil {
        return nil
    }

    slow, fast := head, head
    var prev *ListNode = nil 

    for fast != nil && fast.Next != nil {
        prev = slow
        slow = slow.Next
        fast = fast.Next.Next
    }

    root := &TreeNode{Val: slow.Val}    //1，父节点取中值

    if prev != nil {                    //2，从中点开始，递归左右子树
        prev.Next = nil
        root.Left = sortedListToBST(head)
    }
    root.Right = sortedListToBST(slow.Next)

    return root
}

方法三：从头中序遍历

• 方法1每次获取数组中点花费O(1)O(1)，方法2每次获取链表中点花费O(N)O(N)，时间复杂度更高。
  
• 能更快吗？直接获取头结点最快，不如直接构建它吧！它对应 BST 最左子树的根节点。
  
• 于是我们先构建左子树，再构建根节点，再构建右子树。——遵循中序遍历。
  
• 其实，BST 的中序遍历，打印的节点值正是这个有序链表的节点值顺序。
  
• 如图，维护指针 h，从头结点开始，用 h.val 构建节点，构建一个，指针后移一位。
  

时间复杂度：O(n) == 时间没变
空间复杂度：O(logn) == 空间变小了

var tmp *ListNode

func sortedListToBST(head *ListNode) *TreeNode {
    if head == nil {
        return nil 
    }

    len_list := 0
    tmp = head
    for head != nil {
        len_list++
        head = head.Next
    }

    return buildBST(0, len_list - 1)    //找到建树的 左右范围
}


func buildBST(start, end int ) *TreeNode {
    if start > end {
        return nil
    }

    mid := (start + end) / 2
    left := buildBST(start,mid-1)

    root := &TreeNode{Val: tmp.Val}     //取到链表的值，作为父节点
    tmp = tmp.Next                     //链表依次向前进

    root.Left = left                    //因为是有序，中序构建树
    root.Right = buildBST(mid+1, end)

    return root
}