## 题目地址(109. 有序链表转换二叉搜索树)

https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/

## 题目描述

```
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5
```

## 前置知识

- 递归
- 二叉搜索树
  > 对于树中任意一个点，当前节点的值必然大于所有左子树节点的值
  > 同理,当前节点的值必然小于所有右子树节点的值

## 思路

1. 获取当前链表的中点
2. 以链表中点为根
3. 中点左边的值都小于它,可以构造左子树,
4. 同理构造右子树
5. 循环第一步

### 双指针法

1. 定义一个快指针每步前进两个节点，一个慢指针每步前进一个节点
2. 当快指针到达尾部的时候，正好慢指针所到的点为中点

- 语言支持: JS, Java

JS Code:

```js
var sortedListToBST = function (head) {
  if (!head) return null;
  return run(head, null);
};

function run(head, tail) {
  if (head == tail) return null;
  let fast = head;
  let slow = head;
  while (fast != tail && fast.next != tail) {
    fast = fast.next.next;
    slow = slow.next;
  }
  let root = new TreeNode(slow.val);
  root.left = run(head, slow);
  root.right = run(slow.next, tail);
  return root;
}
```

Java Code:

```java
class Solution {
 public TreeNode sortedListToBST(ListNode head) {
     if(head == null) return null;
     return run(head,null);
 }
 private TreeNode run(ListNode head, ListNode tail){
     if(head == tail) return null;
     ListNode fast = head, slow = head;
     while(fast != tail && fast.next != tail){
         fast = fast.next.next;
         slow = slow.next;
     }
     TreeNode root = new TreeNode(slow.val);
     root.left = run(head, slow);
     root.right = run(slow.next, tail);
     return root;
 }
}
```

**复杂度分析**

- 时间复杂度：节点最多只遍历 N\*logN 遍，时间复杂度为$O(NlogN)$
- 空间复杂度：空间复杂度为$O(1)$

### 缓存法

因为链表访问中点的时间复杂度为 O(n),所以可以使用数组将链表的值存储,以空间换时间

### 代码

- 代码支持: JS, Go, PHP

JS Code:

```js
var sortedListToBST = function (head) {
  let res = [];
  while (head) {
    res.push(head.val);
    head = head.next;
  }
  return run(res);
};

function run(res) {
  if (res.length == 0) return null;
  let mid = parseInt(res.length / 2);
  let root = new TreeNode(res[mid]);
  root.left = mid > 0 ? run(res.slice(0, mid)) : null;
  root.right = mid >= res.length - 1 ? null : run(res.slice(mid + 1));
  return root;
}
```

Go Code:

```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 {
	var a []int
	for head != nil {
		a = append(a, head.Val)
		head = head.Next
	}
	return BST109(a)

}
func BST109(a []int) *TreeNode {
	if len(a) == 0 {
		return nil
	}
	mid := len(a) / 2
	root := &TreeNode{Val: a[mid]}
	root.Left = BST109(a[:mid]) // 递归构建左侧 BST
	root.Right = BST109(a[mid+1:]) // 递归构建右侧 BST
	return root
}
```

PHP Code:

```php
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution
{

    /**
     * @param ListNode $head
     * @return TreeNode
     */
    function sortedListToBST($head)
    {
        $arr = [];
        while ($head) {
            $arr[] = $head->val;
            $head = $head->next;
        }
        return $this->BST($arr);
    }

    function BST(array $arr)
    {
        if (!$arr) return null;
        $mid = (int)(count($arr) / 2);
        $root = new TreeNode($arr[$mid]);
        $root->left = $this->BST(array_slice($arr, 0, $mid));
        $root->right = $this->BST(array_slice($arr, $mid + 1));
        return $root;
    }
}
```

**复杂度分析**

- 时间复杂度：节点最多只遍历两遍，时间复杂度为$O(N)$
- 空间复杂度：若使用数组对链表的值进行缓存，空间复杂度为$O(N)$
