No. 108 - Convert Sorted Array to Binary Search Tree
====


---

## [LeetCode 108 - Convert Sorted Array to Binary Search Tree](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.

---

本題的目的是要將一個由小到大的數列轉換成 Binary Search Tree (BST)。BST 的定義是 tree 中的每一個 node 其左 subtree 的所有 nodes 都要比它小，其右 subtree 的所有 node 都要比它大，同時它的左右 subtree 也要是 BST。

另外，其實只要把 BST 壓扁來看也就是一個由小到大的數列。

題目還有要求轉換成的 BST 要是 height-balanced 也就是要左右 subtree 的高相差不超過 1。

### 解法

下面為完整的程式碼，我們用 recursive 的方式來解。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  TreeNode *_sortedArrayToBST(vector<int> &nums, int start, int end) {
    if (start >= end)
      return NULL;
    int mid = (start + end) / 2;
    TreeNode *node = new TreeNode(nums[mid]);
    node->left = _sortedArrayToBST(nums, start, mid);
    node->right = _sortedArrayToBST(nums, mid + 1, end);
    return node;
  }
  TreeNode* sortedArrayToBST(vector<int>& nums) {
    return _sortedArrayToBST(nums, 0, nums.size());
  }
};

每一次的 recursive 都是在選擇要當 parent 的 node 然後再分成左右兩邊的數列並各自繼續做 recursive。

因為有要求要是 height-balanced BST，為了要讓左右 subtree 的高度相當，我們每次選擇的 parent 都是數列的中間，也就是程式的遞 17 - 18 行。

程式第 19, 20 行就是繼續往下一層 tree 選擇 parent，這其實也就是要建立出左右的 subtree。

現在我們要談談怎麼選擇 `_sortedArrayToBST` 的 `start` 跟 `end`。

每次呼叫 `_sortedArrayToBST` 需要給數列的開頭跟結尾，這邊結尾要給的值是下一次進入函式時不會被選的 node 位置。什麼意思呢? 假設今天給一個下面的數列，第一次呼叫函式，我們給的開頭是 0，結尾會是給 5 也就是這個數列的大小，並不是給第四個位置。這樣在第 17 行算出來的中間結果會是 2。

val: 1 2 3 4 5
idx: 0 1 2 3 4

接著要繼續做 recursive，左邊的數列就會是 `_sortedArrayToBST(nums, start, mid)`，結尾是拿在這次被選擇的 node 的位置，因為這在接下來被呼叫的函式是不會被選到的。而右邊數列就會是 `_sortedArrayToBST(nums, mid + 1, end)`，開頭是拿這次被選擇的 node 的下一個位置，這個位置在下一次函式裡是會被選擇的 node，至於 `end` 則同樣是數列的大小是不存在 node 的位置。

由這樣的方法選擇開頭跟結尾，我們判斷這個 recursive 何時結束的標準就是當 `start >= end`，這個開頭結尾的給法會在當開頭的位置**等於**結尾的位置時也會結束。

為什麼遇到等於的情況就要結束? 我們可以這樣想:
『由於我們一開始給的結尾是一個不存在的值，這個值會一直在選擇右邊數列時傳遞下去，所以最後肯定會遇到開頭等於結尾的位置的時候。因為結尾位置是不存在的，所以遇到這種情況就不應該繼續呼叫函式。』

----

如果結尾位置改成給最後一個值的位置的話，那程式碼的寫法就會如下面所示。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  TreeNode *_sortedArrayToBST(vector<int> &nums, int start, int end) {
    if (start > end)
      return NULL;
    int mid = (start + end) / 2;
    TreeNode *node = new TreeNode(nums[mid]);
    node->left = _sortedArrayToBST(nums, start, mid - 1);
    node->right = _sortedArrayToBST(nums, mid + 1, end);
    return node;
  }
  TreeNode* sortedArrayToBST(vector<int>& nums) {
    return _sortedArrayToBST(nums, 0, nums.size() - 1);
  }
};

跟前面的程式碼不同的地方在第 15, 19, 24 行。在第一次呼叫 `_sortedArrayToBST` 函式時，結尾要給的是數列大小減 1 的位置 (第 24 行)，也就是數列的最後一個值。而之後每次呼叫 `_sortedArrayToBST` 左邊數列的結尾都是要給 `mid - 1` 的位置 (第 19 行)，這樣才是滿足前面的改動 -- 『結尾位置改成給最後一個值的位置』。

而這個改動會影響的還有最後 recursive 結束的判斷，也就是第 15 行。跟前面的判斷不同，這次不會再開頭位置等於結尾位置時就結束 recursive，**因為結尾的位置不再是不能被選擇的位置**。

### 複雜度分析

時間複雜度為 $O(N)$，$N$ 為數列的大小，因為要轉成 BST 就需要把數列的每個值都走訪一遍。

空間複雜度為 $O(H)$，$H$ 為 BST 的高，因為是 recursive 的呼叫函式，所以最多會存 BST 高度的函式在儲存函式的 stack 裡。