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
考え方
rootがnoneの状態のときにleft,,rightにアクセスするとエラーになるので先に例外処理をします。
isMirrorという二分木を比較する関数を作り、left,rightを代入します
ismirrorの中でどちらもnoneだったらtrue,どちらかだけがnoneだったらfalseとします。
あとは再帰処理を用いてぐるぐると回していきます
解答コード
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
}
}
Author And Source
この問題について(LeetCodeに毎日挑戦してみた 101 Symmetric Tree(Python、Go)), 我々は、より多くの情報をここで見つけました https://qiita.com/ishishow/items/a4001150646065f641f1著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .