ゼロから始めるLeetCode Day100「108. Convert Sorted Array to Binary Search Tree」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day99 「112. Path Sum」

次回
ゼロから始めるLeetCode Day101「387. First Unique Character in a String

Twitterやってます。

問題

108. Convert Sorted Array to Binary Search Tree
難易度はEasy。
コーディング面接対策のために解きたいLeetCode 60問からの抜粋です。

問題としては、要素が昇順にソートされた配列が与えられた場合，それを高さバランスのとれた二分探索木に変換してください、というものです。
この問題では、二分探索木とは，各ノードの2つの部分木の深さが1以上異なることがない二分木と定義されます。

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

解法

# 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]) -> TreeNode:
        if not nums:
            return None
        mid = len(nums)//2
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        if mid < len(nums)-1:
            root.right = self.sortedArrayToBST(nums[mid+1:])
        return root

再帰の典型的なような問題だったので、それぞれの右側と左側にソートされた配列の中間の値で区切ったものを次々と代入していく、というようにしました。

最終的には配列の要素を全て追加し終わった後にrootを返し、終了です。

では今回はここまで。お疲れ様でした。