题目描述:
给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表: [-10, -3, 0, 5, 9],
一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树:
0
/ \
-3 9
/ /
-10 5
题目分析:从一个有序的链表中构建二叉搜索树
解题思路:使用三个指针slowPoint(慢指针),fastPoint(快指针),lastPoint(最后一个元素的指针),slowPoint每次移动一个元素(lastPoint和慢指正相同),fastPoint每次移动两个元素,当fastPoint移动到链表尾部的时候,slowPoint指针将会处于链表中的中间元素,之后将lastPoint的下一元素设置为空,起到分割链表的作用,再对分割出的两个链表进行递归。最后返回数的根节点。
func sortedListToBST(head *ListNode) *TreeNode {
if head == nil {
return nil
}
if head.Next == nil {
return &TreeNode{Val:head.Val}
}
slowPoint := head
fastPoint := head
lastPoint := slowPoint
for fastPoint.Next != nil && fastPoint.Next.Next != nil{
lastPoint = slowPoint
fastPoint = fastPoint.Next.Next
slowPoint = slowPoint.Next
}
fastPoint = slowPoint.Next
lastPoint.Next = nil
currenNode := &TreeNode{Val:slowPoint.Val}
if head != slowPoint {
currenNode.Left = sortedListToBST(head)
}
currenNode.Right = sortedListToBST(fastPoint)
return currenNode
}