24. Convert Sorted Array to Binary Search Tree

読了目安 約2分

Tree / LC 108 (Easy) — ソート済み配列から高さ平衡な BST を作る。

問題

LeetCode 108. Convert Sorted Array to Binary Search Tree（Easy / カテゴリ: Tree）

昇順にソートされた整数配列 nums を、高さ平衡な二分探索木に変換して根を返します。 二分探索木（BST）は、どのノードでも「左の部分木のすべての値 < ノードの値 < 右の部分木のすべての値」が成り立つ二分木です。 高さ平衡とは、すべてのノードで左右の部分木の高さの差が 1 以下という条件です。 答えは一意ではないため、このページのテストは「中間順走査がソート列と一致する」「すべてのノードで左右の部分木の高さの差が 1 以下」の 2 つの性質で採点します。

考え方

Swift 実装のポイント

• 部分配列を Array(nums[lo...mid]) のように切り出すとコピーが発生します。添字の範囲を引数に取る再帰にすると O(N) で済みます。
• メソッドの中に func build(_ lo: Int, _ hi: Int) -> TreeNode? を定義すると、nums を引き回さずに書けます。
• 中央の添字は (lo + hi) / 2 です。lo > hi が空の部分木のベースケースです。

class Solution {
    func sortedArrayToBST(_ nums: [Int]) -> TreeNode? {
        func build(_ lo: Int, _ hi: Int) -> TreeNode? {
            if lo > hi { return nil }
            let mid = (lo + hi) / 2
            let node = TreeNode(nums[mid])
            node.left = build(lo, mid - 1)
            node.right = build(mid + 1, hi)
            return node
        }
        return build(0, nums.count - 1)
    }
}