LeetCodeに毎日挑戦してみた 101 Symmetric Tree(Python、Go)


Leetcodeとは

leetcode.com
ソフトウェア開発職のコーディング面接の練習といえばこれらしいです。
合計1500問以上のコーデイング問題が投稿されていて、実際の面接でも同じ問題が出されることは多いらしいとのことです。

golang入門+アルゴリズム脳の強化のためにgoとPythonで解いていこうと思います。(Pythonは弱弱だが経験あり)

22問目(問題101)

101 Symmetric Tree

問題内容

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

(日本語訳)

二分木が与えられたら、それがそれ自体の鏡であるかどうか(つまり、その中心を中心に対称であるかどうか)を確認します。。

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

考え方

  1. rootがnoneの状態のときにleft,,rightにアクセスするとエラーになるので先に例外処理をします。

  2. isMirrorという二分木を比較する関数を作り、left,rightを代入します

  3. ismirrorの中でどちらもnoneだったらtrue,どちらかだけがnoneだったらfalseとします。

  4. あとは再帰処理を用いてぐるぐると回していきます

解答コード

class Solution:
  def isSymmetric(self, root):
    if root is None:
      return True
    else:
      return self.isMirror(root.left, root.right)

  def isMirror(self, left, right):
    if left is None and right is None:
      return True
    if left is None or right is None:
      return False

    if left.val == right.val:
      outPair = self.isMirror(left.left, right.right)
      inPiar = self.isMirror(left.right, right.left)
      return outPair and inPiar
    else:
      return False
  • Goでも書いてみます!
func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return isSameTree(root.Left, root.Right)
}

func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p != nil && q != nil {
        return p.Val == q.Val && isSameTree(p.Left, q.Right) && isSameTree(p.Right, q.Left)
    } else {
        return p == q
    }
}