Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

提示	解題應用
DepthFirstSearch	InorderTravel
LinkedList	Pointer

Default:

/**
 * 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 {

}

解答思路:

建議可以先參考先前Convert Sorted Array to Binary Search Tree的解法，解說較為詳細，基本上概念完全一樣，只是將先前題的程式碼稍做修改而已，如果能將排序陣列還原回二元搜尋、平衡樹，當然要將排序LinkedList也還原回二元搜尋、平衡樹就不會太困難。

排序陣列與排序LinkedList最大的差異是陣列能直接取出中間值來當作根節點，LinkedList只能先遍歷之後才能找出中間值，其實也不過是多了這一點點的難度而已，只要同時以快、慢(速度2:1，快的一次遍歷兩個節點，慢的一次只遍歷一個節點)兩個指標同時遍歷LinkedList，最後當比較快的指標到達LinkedList最後一個節點，此時比較慢的指標就會指向中間值的節點了，而知道LinkedList的中間值之後，剩下的處理方式就沒有什麼太大差異。

程式碼解說:

這邊最初也是直接將由小至大排序好的LinkedList帶入遞回函數之中來還原回二元搜尋樹

func sortedListToBST(head *ListNode) *TreeNode {
	return construct(head)
}

接著一樣處理遞回的細節，因為空節點、1個節點的情況與2個節點(包含)以上的情況處理方法完全不同，所以一開始要先針對前兩個情況做處理，如果進來的節點為空就直接回傳空的節點位址，而如果進來的節點只有1個(下一個節點位置為空)，則將其做為新建的根節點回傳，再來便開始同時以快、慢(速度2:1)兩個指標同時遍歷LinkedList，兩個指標的初始位置當然分別是第1、2個節點，直到比較快的指標到達LinkedList最後一個節點才停止迴圈，這邊要注意到的是比較快的指標如果後頭的節點數不足兩個一樣停止遍歷，如此一來就可以讓比較慢的指標停在中間節點的前一個，因為中間節點之前的所有節點屬於左子樹，要記得將該串最後一個節點的下一個位置改為nil才能往下遞回(帶入整串LinkedList，也就是第一個節點的位置)，右子樹的還原則是帶入根節點的下一個位置到遞回函數，待兩側子樹的位址回來，最後才向上回傳新建的根節點位址並嫁接左右子樹

func construct(head *ListNode) *TreeNode {
	if head == nil {
		return nil
	} else if head.Next == nil {
		return &TreeNode{head.Val, nil, nil}
	}
	slow := head
	fast := head.Next
	for fast != nil && fast.Next != nil && fast.Next.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	root := slow.Next
	slow.Next = nil
	left := construct(head)
	right := construct(root.Next)
	return &TreeNode{root.Val, left, right}
}

完整程式碼:

func sortedListToBST(head *ListNode) *TreeNode {
	return construct(head)
}
func construct(head *ListNode) *TreeNode {
	if head == nil {
		return nil
	} else if head.Next == nil {
		return &TreeNode{head.Val, nil, nil}
	}
	slow := head
	fast := head.Next
	for fast != nil && fast.Next != nil && fast.Next.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	root := slow.Next
	slow.Next = nil
	left := construct(head)
	right := construct(root.Next)
	return &TreeNode{root.Val, left, right}
}

總結:

建議可以先參考先前Convert Sorted Array to Binary Search Tree的解法，解說較為詳細，基本上概念完全一樣，只是這次是要將排序LinkedList也還原回二元搜尋、平衡樹而非排序陣列，兩者最大的差異是陣列能直接取出中間值來當作根節點，不過LinkedList只要同時以快、慢(速度2:1，快的一次遍歷兩個節點，慢的一次只遍歷一個節點)兩個指標同時遍歷LinkedList，最後當比較快的指標到達LinkedList最後一個節點，此時比較慢的指標就會指向中間值的節點了，而知道LinkedList的中間值之後，剩下的處理方式就沒有什麼太大差異。