109. 有序链表转换二叉搜索树

题意：

解题思路：

思路：O(log(n))
1. 快慢指针找到链表中间节点，用来作为树的根节点；
2. 递归链表左边构建左子树，递归右边构建右子树；

PHP代码实现：

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    /**
     * @param ListNode $head
     * @return TreeNode
     */
    function sortedListToBST($head) {
        //return $this->helper($head, null);
        $nums = [];
        while ($head != null) {
            $nums[] = $head->val;
            $head = $head->next;
        }
        return $this->helper($nums, 0, count($nums) - 1);
    }
    function helper($nums, $left, $right) {
        if ($left > $right) return null;
        $mid = $left + floor(($right - $left)/2);
        $node = new TreeNode($nums[$mid]);
        $node->left = $this->helper($nums, $left, $mid-1);
        $node->right = $this->helper($nums, $mid+1, $right);
        return $node;
    }
    function sortedListToBST1($head) {
        if($head == null) return null;
        $mid = $this->getMidNode($head);
        $node = new TreeNode($mid->val);
        if($mid == $head){
            return $node;
        }
        $node->left = $this->sortedListToBST($head);
        $node->right = $this->sortedListToBST($mid->next);
        return $node;
    }
    function getMidNode(&$head){
        $prePtr = null;
        $slowPtr = $head;
        $fastPtr = $head;
        while($fastPtr!=null && $fastPtr->next!=null){
            $prePtr = $slowPtr;
            $slowPtr = $slowPtr->next;
            $fastPtr = $fastPtr->next->next;
        }
        if($prePtr!=null){
            $prePtr->next = null;
        }
        return $slowPtr;
    }
    function helpers($head, $tail) {
        if ($head == null || $head == $tail) {
            return null;
        }
        $slow = $head;
        $fast = $head;
        while ($fast->next != $tail && $fast->next->next != $tail) {
            $fast = $fast->next->next;
            $slow = $slow->next;
        }
        $current = new TreeNode($slow->val);
        $current->left = $this->helper($head, $slow);
        $current->right = $this->helper($slow->next, $tail);
        return $current;
    }
}

GO代码实现：

/**
 * 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 {
    nums, p := []int{}, head
    for p != nil {
        nums, p = append(nums, p.Val), p.Next
    }
    return helper(nums, 0, len(nums)-1)
}
func helper(nums []int, l, r int) *TreeNode {
    if l > r {
        return nil
    }
    mid := (l + r) / 2
    root := &TreeNode{Val: nums[mid]}
    root.Left, root.Right = helper(nums, l, mid-1), helper(nums, mid+1, r)
    return root
}

func sortedListToBST(head *ListNode) *TreeNode {
    return buildtree(head, nil)
}
func buildtree(head, tail *ListNode) *TreeNode {
    if head == tail {
        return nil
    }
    slow, fast := head, head
    for fast != tail && fast.Next != tail {
        slow = slow.Next
        fast = fast.Next.Next
    }
    root := &TreeNode{Val: slow.Val}
    root.Left = buildtree(head, slow)
    root.Right = buildtree(slow.Next, tail)
    return root
}