---
title: 109. Convert Sorted List to Binary Search Tree
tags: Leetcode,2021
---
# 【LeetCode】109. Convert Sorted List to Binary Search Tree
## Description
>Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

>For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

>給予一個單向的串列鏈結且元素已經經過漸增排序，將它轉換為高度平衡的二元搜索樹(BST)。

這個問題中，所謂的高度平衡的二元樹被定義為一棵二元樹中所有節點的兩個子樹高度差異不大於一。
## Example

Example 1:
Input: head = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.
Example 2:

Input: head = []
Output: []
Example 3:

Input: head = [0]
Output: [0]
Example 4:

Input: head = [1,3]
Output: [3,1]

## Constraints:

The number of nodes in head is in the range [0, 2 * 104].
-10^5 <= Node.val <= 10^5

## Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public TreeNode SortedListToBST(ListNode head) {
        var list = Build(head);
        return Build(list, 0, list.Length);
    }
    
    private TreeNode Build(int[] list, int lower, int upper) {
        if (lower + 1 == upper) return new TreeNode(list[lower]);
        if (lower >= upper) return null;
        var mid = (lower + upper) / 2;
        return new TreeNode(list[mid], Build(list, lower, mid), Build(list, mid + 1, upper));
    }
    
    private int[] Build(ListNode head) {
        var node = head;
        var list = new List<int>();
        while (node != null) {
            list.Add(node.val);
            node = node.next;
        }
        return list.ToArray();
    }
}