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
headis 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:]),
}
}