【每日一题】- 2019-08-27 - 109. 有序链表转换二叉搜索树

[watchpoints]

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[watchpoints]

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedListToBST(head *ListNode) *TreeNode {
    if head == nil {
        return nil
    }
    lenList := 0
    cur := head

    for cur != nil {
        cur = cur.Next
        lenList++
    }

    return binarySearch(&head, 0, lenList-1)

}

func binarySearch(head **ListNode, start int, end int) *TreeNode {
    if start > end {
        return nil //
    }

    mid := (start + end) / 2
    left := binarySearch(head, start, mid-1)
    root := &TreeNode{(*head).Val, nil, nil}
    root.Left = left
    *head = (*head).Next

    //order must leftSubTree, head ,rightSubTree
    right := binarySearch(head, mid+1, end)
    root.Right = right

    return root
}

复杂度分析

• 时间复杂度： 时间复杂度仍然为 O(N) 因为我们需要遍历链表中所有的顶点一次并构造相应的二叉搜索树节点。

• 空间复杂度： O(logN)

[watchpoints]

触类旁通： [编程题]二叉搜索树与双向链表

来源：