Problem Description

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

Link

Solution 1

We can use Slow and Fast pointer to solve this issue, We need to get the root node first, and then get its leftChild and rightChild recursively.

Code

func sortedListToBST(head *ListNode) *TreeNode {
	if head == nil { return nil}
	if head.Next == nil{
		return &TreeNode{
			Val: head.Val,
		}
	}
	var slow_prev *ListNode
	slow, fast := head, head
	
	for fast != nil && fast.Next != nil {
		slow_prev = slow
		slow = slow.Next
		fast = fast.Next.Next
	}
	slow_prev.Next = nil
	root := &TreeNode{
		Val: slow.Val,
	}
	root.Left = sortedListToBST(head)
	root.Right = sortedListToBST(slow.Next)
	return root
}

Time Complexity: O(nlogn)

Space Complexity: O(logn)

Solution 2

We can convert the Linked List to Array first, and then build the BST, actually it’s kind of like Slow and Fast Pointer

Code

func sortedListToBST(head *ListNode) *TreeNode {
	var nums []int
	for head != nil {
		nums = append(nums, head.Val)
		head = head.Next
	}
	return buildBST(nums, 0, len(nums))
}

func buildBST(nums []int, left, right int) *TreeNode {
	if left > right {
		return nil
	}
	mid := (left + right) / 2
	root := &TreeNode{
		Val: nums[mid],
	}
	root.Left = buildBST(nums, left, mid - 1)
	root.Right = buildBST(nums, mid+1, right)
	
	return root
}

Time Complexity: O(nlogn)

Space Complexity: O(logn)

Solution 3

We could use Inorder traversal to solve this issue, Slow and Fast Pointer is Preorder traversal. For this issue, Inorder traversal is the most efficient way, it can make sure we iterate every element only one time.

And please note that when we build the BST, we must pass **ListNode instead of *ListNode. Because Go uses pass-by-value, if we pass *ListNode, we just pass a copy of *ListNode and the change on it won’t be reflected in outside.

Code

func sortedListToBST(head *ListNode) *TreeNode {
	size := getSize(head)
	
	return buildBST(&head, 0, size - 1)
}

func buildBST(head **ListNode, left, right int) *TreeNode {
	if left > right {
		return nil
	}
	mid := (left + right) / 2
	leftChild := buildBST(head, left, mid - 1)
	root := &TreeNode{
		Val: (*head).Val,
	}
	*head = (*head).Next
	rightChild := buildBST(head, mid+1, right)
	root.Left = leftChild
	root.Right = rightChild
	
	return root
}

func getSize(head *ListNode) int {
	size := 0
	for head != nil {
		size++
		head = head.Next
	}
	return size
}

Time Complexity: O(n)

Space Complexity: O(logn)