ゼロから始めるLeetCode Day23「226. Invert Binary Tree」

概要

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

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

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

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

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

Leetcode

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

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day22「141. Linked List Cycle」
次回
ゼロから始めるLeetCode Day24 「21. Merge Two Sorted Lists」

問題

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.

たまにはこんな感じでさくっと終わってもいいでしょう。
木の練習にはいいと思うのでぜひ解いてみてください。