先說30天挑戰的結論，
看來最後只能停在Tree資料的問題了
蠻可惜得是這30天並沒有包含到所有資料結構和演算法的複習．
每天做一題 Leetcode 最大的挑戰大概是有時比較忙或當天比較累的情況下，真的沒辦法做 Medium 困難度的題目，
而一旦選擇做 easy 的題目，就會連續好幾天只做easy 的題目．
人的惰性真的很可怕．

在做這30題的過程中，我發現有些常用的語法還是要先強迫自己背下來，譬如 Go語言怎麼把 int 轉成 string 等．
不然如果沒有 google ，面試時就會寫不出來．

最後，今天就用 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.

Example 1:
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:
Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

Constraints:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums is sorted in a strictly increasing order.

Hint

binary search tree 是一種 binary tree，而且每個節點的都滿足下列條件：
所有左邊子節點的值 <= 父節點的值 < 所有右邊子節點的值.

我的答案

一個已經排序過的陣列其中間值是root, 左半邊的值就是left subtree，右半邊的值就是right subtree.

[1, 2, 3, 4, 5, 6, 7] -> left: [1, 2, 3], root: 4, right: [5, 6, 7]
[1, 2, 3] -> left: [1], root: 2, right: [3]
[5, 6, 7] -> left: [5], root: 6, right: [7]

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        return self.convert(nums, 0, len(nums)-1)

    def convert(self, nums, left, right):
        if left > right:
            return None
        mid = (left + right) // 2
        node = TreeNode(nums[mid])
        node.left = self.convert(nums, left, mid - 1)
        node.right = self.convert(nums, mid + 1, right)
        return node

Go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func Convert(nums *[]int, left int, right int) *TreeNode {
    if left > right {
        return nil
    }
    mid := (left + right) / 2
    node := TreeNode{}
    node.Val = (*nums)[mid]
    node.Left = Convert(nums, left, mid-1)
    node.Right = Convert(nums, mid+1, right)
    return &node
}

func sortedArrayToBST(nums []int) *TreeNode {
    return Convert(&nums, 0, len(nums)-1)
}