ゼロから始めるLeetCode Day27「101. Symmetric Tree」

概要

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

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

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

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

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

Leetcode

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

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day26「94. Binary Tree Inorder Traversal」
次回
ゼロから始めるLeetCode Day28「198. House Robber」

問題

101. Symmetric Tree
難易度はeasy。
Top 100 Liked Questionsからの抜粋です。

問題としては二分木が与えられるので左右対称であるかを確認してください、というお題です。

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3
 

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

解法

# 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 isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        return self.dfs(root,root)
    
    def dfs(self,left,right):
        if left and right:
            return left.val == right.val and self.dfs(left.left,right.right) and self.dfs(left.right,right.left)
        else:
            return left == right
# Runtime: 32 ms, faster than 71.25% of Python3 online submissions for Symmetric Tree.
# Memory Usage: 13.9 MB, less than 5.17% of Python3 online submissions for Symmetric Tree.

深さ優先探索で解きました。

きちんと左右対象のシンメトリーかを判定しなければならない点に注意しましょう。
あんまり書くことないですね・・・

良さげな解答があれば追記します。