109. Convert Sorted List to Binary Search Tree ⭐

Medium

Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example 1:

Input: head = [-10,-3,0,5,9]
Output:
 [0,-3,9,-10,null,5]
Explanation:
 One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.

Example 2:

Input: head = []
Output:
 []

Constraints:

• The number of nodes in head is in the range [0, 2 * 104].

• -105 <= Node.val <= 105

解題

這題和 108. 題有異曲同工之妙，唯一的差別在於前一題給的是陣列，這一題給的是 Linked list。利用快慢指針和Binary Search 找到中點的技巧來解題。

/**
 * 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 }
    if head.Next == nil {
        return &TreeNode{ Val: head.Val, Left:nil, Right: nil }
    }
    
    var prev *ListNode
	slow, fast := head, head
    
    for fast != nil && fast.Next != nil {
        prev = slow
	slow = slow.Next
	fast = fast.Next.Next
    }
    
    prev.Next = nil
	
    root := &TreeNode{ Val: slow.Val}
    root.Left = sortedListToBST(head)
    root.Right = sortedListToBST(slow.Next)
	
    return root
}

另一個方法是先將 linked list 轉成陣列

/**
 * 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 }
    if head.Next == nil {
        return &TreeNode{ Val: head.Val, Left:nil, Right: nil }
	}
    
    nodes := make([]int, 0)
    for head != nil {
        nodes = append(nodes, head.Val)
        head = head.Next
    }

    return helper(nodes)
}

func helper(nodes []int) *TreeNode {
    l := len(nodes)
    if l == 0 { return nil }
    if l == 1 { return &TreeNode{ Val: nodes[0], Left:nil, Right: nil } }

    mid := l / 2
    return &TreeNode{
        Val: nodes[mid],
        Left: helper(nodes[0:mid]),
        Right: helper(nodes[mid+1:]),
    }
}