ゼロから始めるLeetCode Day9「701. Insert into a Binary Search Tree」

概要

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

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

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

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

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

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day8 「1302. Deepest Leaves Sum」
次回
ゼロから始めるLeetCode Day10 「1431. Kids With the Greatest Number of Candies」

問題

701. Insert into a Binary Search Tree

またしても木の問題とタイトルでわかるような問題ですね。

見ての通り二分探索木が与えられるのでその木に正しく数字を挿入し、挿入後の木を返すという問題です。

# 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 insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        if root is None:
            return TreeNode(val)
        if root.val > val:
            root.left = self.insertIntoBST(root.left, val)
        elif root.val < val:
            root.right =  self.insertIntoBST(root.right, val)
        return root
# Runtime: 124 ms, faster than 99.95% of Python3 online submissions for Insert into a Binary Search Tree.
# Memory Usage: 15.9 MB, less than 8.00% of Python3 online submissions for Insert into a Binary Search Tree.

二分探索木の性質を利用して、rootのvalの値とvalで比較し、rootの方が大きければ左に、そうでなければ右に再帰的な処理を行い、処理が終わったときにrootを返すという単純なのを書きました。
書く前に思っていたよりシンプルな答えになりました。