- Convert Sorted List to Binary Se
- Convert Sorted List to Binary Se
- Convert Sorted List to Binary Se
- convert-sorted-list-to-binary-se
- 每天一道leetcode109-有序链表转换为二叉搜索树
- Leetcode-108Convert Sorted Array
- 108. Convert Sorted Array to Bin
- leetcode:108. Convert Sorted Arr
- Leetcode PHP题解--D95 108. Convert
- 109. Convert Sorted List to Bina
解决思路：
由于单链表是有序的，可以找到中间位置的元素，作为树的根节点，那么单链表的左半边就是左子树，右半边就是右子树，对于子树，同样是将一个单链表生成一个BST问题，递归方式即可解决问题。针对寻找单链表中的中间位置元素，可以使用两个指针遍历，slow每次走一步，fast每次走两步，fast走到链表尾，slow就是中间位置元素。
代码示例：
```
/**
* 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
}
middle, pre := getMiddleAndPre(head)
// 如果前一个节点为nil，说明中间节点就是头节点，那么做左孩子应该为空，
//故设置head为nil, 递归调用；否则应该将链表断开
if pre == nil {
head = nil
}else{
pre.Next = nil
}
return &TreeNode{
Val : middle.Val,
Left : sortedListToBST(head),
Right: sortedListToBST(middle.Next),
}
}
func getMiddleAndPre(head *ListNode) (middle, pre *ListNode) {
slow := head
fast := head
for fast != nil && fast.Next != nil {
pre = slow
slow = slow.Next
fast = fast.Next.Next
}
//返回值为中间位置的节点和前一个节点，前一个节点用于断开单链表
//才能正确完成递归调用
return slow, pre
}
```
网友评论