0109. Convert Sorted List to Binary Search Tree | LeetCode Cookbook

[halfrost]

https://books.halfrost.com/leetcode/ChapterFour/0100~0199/0109.Convert-Sorted-List-to-Binary-Search-Tree/

[guuzaa]

func sortedListToBST(head *ListNode) *TreeNode {
	if head == nil {
		return nil
	}
	if head != nil && head.Next == nil {
		return &TreeNode{Val: head.Val, Left: nil, Right: nil}
	}
	middleNode, preNode := middleNodeAndPreNode(head)
       // 为什么要判断 middleNode 是否为空? middleNodeAndPreNode  返回 mid 为空只有两种情况：head 是空，或者 head.Next 为空
      // 可是这两种情况都在上面做了特判，所以，可以删掉下面的 if 语句
	if middleNode == nil {
		return nil
	}
	if preNode != nil {
		preNode.Next = nil
	}
	if middleNode == head {
		head = nil
	}
	return &TreeNode{Val: middleNode.Val, Left: sortedListToBST(head), Right: sortedListToBST(middleNode.Next)}
}