3
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

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

Posted at

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

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

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

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

Leetcode

ゼロから始める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.

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

3
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
3
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?