概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
その対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。
せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
前回
ゼロから始めるLeetCode Day22「141. Linked List Cycle」
基本的にeasyのacceptanceが高い順から解いていこうかと思います。
Twitterやってます。
問題
226. Invert Binary Tree
難易度はeasy。
Top 100 Liked Questionsからの抜粋です。
Top 100 Liked Questionsのeasyも残り10問となりました、もっと勉強進めてMediumくらいはさくっと解けるようになりたいですね。
問題としては与えられた二分木の構造をそっくりそのまま反転させるというものです。
Example:
Input:
4
/ \
2 7
/ \ / \
1 3 6 9
Output:
4
/ \
7 2
/ \ / \
9 6 3 1
見ればわかると思うので特に解説はないです。
解法
それぞれの子以下を反転させて最後に右と左の子を入れ替えれば良いので、この問題は右側と左側を分けて考えるとわかりやすいです。
よくある再帰で書きました。
# 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 invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return None
right = self.invertTree(root.right)
left = self.invertTree(root.left)
root.left = right
root.right = left
return root
# Runtime: 28 ms, faster than 74.30% of Python3 online submissions for Invert Binary Tree.
# Memory Usage: 13.8 MB, less than 5.41% of Python3 online submissions for Invert Binary Tree.
たまにはこんな感じでさくっと終わってもいいでしょう。
木の練習にはいいと思うのでぜひ解いてみてください。