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

概要

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

その対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。

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

Leetcode

基本的にeasyのacceptanceが高い順から解いていこうかと思います。

前回
ゼロから始めるLeetCode Day8 「1302. Deepest Leaves Sum」

問題

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を返すという単純なのを書きました。
書く前に思っていたよりシンプルな答えになりました。