# 108. Convert Sorted Array to Binary Search Tree

### Leetcode

<https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/>

### 題目

Given an integer array `nums` where the elements are sorted in **ascending order**, convert *it to a **height-balanced** binary search tree*.

A **height-balanced** binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/02/18/btree1.jpg)

```
Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2021/02/18/btree.jpg)

```
Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.
```

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

這題根據子樹排序的方式有多種的解答

方法一的方式為&#x20;

Choose Left Middle Node as a Root (每次挑選中間值時都選偏左的)

input: \[-10, -3, 0, 5, 9]

ans: \[0, -10, 5, null, -3, null, 9]

```
var sortedArrayToBST = function(nums) {
    const getNode = (left, right) => {
        if (left > right) return null;
        
        const mid = Math.floor((left + right) / 2);
        const val = nums[mid];
        const node = new TreeNode(val);
        
        node.left = getNode(left, mid - 1);
        node.right = getNode(mid + 1, right);
        return node;
    }
    
    return getNode(0, nums.length - 1);
};
```

Runtime: 129 ms, faster than 15.88% of JavaScript online submissions for Convert Sorted Array to Binary Search Tree.

Memory Usage: 44.6 MB, less than 53.40% of JavaScript online submissions for Convert Sorted Array to Binary Search Tree.

* **方法二**

Choose Right Middle Node as a Root (每次挑選中間值時都選偏左的)

input: \[-10, -3, 0, 5, 9]

ans: \[0, -3, 9, -10, null, 5]

```
var sortedArrayToBST = function(nums) {
    const getNode = (left, right) => {
        if (left > right) return null;
        
        const mid = Math.ceil((left + right) / 2);
        const val = nums[mid];
        const node = new TreeNode(val);
        
        node.left = getNode(left, mid - 1);
        node.right = getNode(mid + 1, right);
        return node;
    }
    
    return getNode(0, nums.length - 1);
};
```

Runtime: 92 ms, faster than 64.34% of JavaScript online submissions for Convert Sorted Array to Binary Search Tree.

Memory Usage: 44.9 MB, less than 30.59% of JavaScript online submissions for Convert Sorted Array to Binary Search Tree.
