LeetCode 109. 有序链表转换二叉搜索树
题目描述
思路分析
将有序链表转换为二叉搜索树的关键在于找到链表的中间节点作为树的根节点。
可以使用快慢指针法来找到链表的中间节点。快指针每次移动两步，慢指针每次移动一步，当快指针到达链表末尾时，慢指针正好位于链表的中间位置。
然后递归地对链表的左半部分和右半部分进行相同的操作，构建左子树和右子树。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func sortedListToBST(head *ListNode) *TreeNode {
if head == nil {
return nil
}
slow, fast := head, head
var pre *ListNode
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
pre = slow
slow = slow.Next
}
if pre != nil {
pre.Next = nil
}
mid := slow
root := &TreeNode{Val: mid.Val}
if head == mid {
return root
}
root.Left = sortedListToBST(head)
root.Right = sortedListToBST(mid.Next)
return root
}
- 时间复杂度：O (n)，其中 n 是链表的长度。
- 空间复杂度：O (log n)，递归栈的深度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func findMiddle(head *ListNode) *ListNode {
var pre *ListNode
slow, fast := head, head
for fast != nil && fast.Next != nil {
pre = slow
slow = slow.Next
fast = fast.Next.Next
}
if pre != nil {
pre.Next = nil // 切断链表
}
return slow
}
func sortedListToBST(head *ListNode) *TreeNode {
if head == nil {
return nil
}
mid := findMiddle(head)
root := &TreeNode{Val: mid.Val}
if head == mid {
return root
}
root.Left = sortedListToBST(head)
root.Right = sortedListToBST(mid.Next)
return root
}
- 时间复杂度：O (n)，其中 n 是链表的长度。
- 空间复杂度：O (log n)，递归栈的深度。
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！