🖋
LeetCode 108. Convert Sorted Array to Binary Search Tree
はじめに
LeetCode 「108. Convert Sorted Array to Binary Search Tree」の問題をGoで解きました。
問題
問題文
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.
和訳
要素が昇順に並べられた整数配列 nums が与えられたら、それを高さバランスのとれた二分探索木に変換します。
高さバランスのとれた二分木は、各ノードの 2 つのサブツリーの深さが 1 以上異なることがない二分木です。
例
0
/ \
-3 9
/ /
10 5
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:
0
/ \
-10 5
\ \
-3 9
3 1
/ \
1 3
Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.
制約
- 1 <= nums.length <= 104
- -104 <= nums[i] <= 104
- nums is sorted in a strictly increasing order.
解答
与えられた配列から、高さのバランスがとれた二分探索木を作る問題です。
配列は昇順になっています。
二分探索木は中間順でたどると、値の昇順となるため、ルートは配列の中央の値となります。
中央を根にして、左半分を使って左部分木を再帰的に構築・右半分を使って右部分木を再帰的に構築することで解くことができます。
この手法では、常に中央の値ルートにすることで、左右の部分木の要素数が均等に近くなります。
これにより、木の高さができるだけ小さくなり、高さのバランスが保たれます。
コード
func sortedArrayToBST(nums []int) *TreeNode {
if len(nums) == 0 {
return nil
}
mid := (len(nums) / 2) // 中央を選ぶ
root := &TreeNode{Val: nums[mid]} // 中央をルートに
root.Left = sortedArrayToBST(nums[:mid])
root.Right = sortedArrayToBST(nums[mid+1:])
return root
}
計算量
- 時間的計算量：O(n)
- 配列の要素全てを1回ずつ処理するため
- 空間的計算量：O(log n)平均 ~ O(n)最悪
- 再起呼び出しの深さが木の高さに比例する
参考
二分木の問題は、以下の記事でも紹介していますので、参考にしてください。
Discussion