LeetCode / Symmetric Tree
https://leetcode.com/problems/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:
But the following [1,2,2,null,3,null,3] is not:
Note:
Bonus points if you could solve it both recursively and iteratively.
前回記事のSame Treeに続き、バイナリツリーを扱った問題。
今度はSymmetric、つまり左右対照の図形かどうかを判定します。
ボーナスポイントをくれるとのことですし、recursiveな解法とiterativeな解法の両方を探してみましょう。
解答・解説
解法1
recursiveな解法。
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def isSymmetric(self, root): if not root: return True else: return self.isMirror(root.left, root.right) def isMirror(self, left, right): if not left and not right: return True if not left or not right: 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
2つ関数を定義していますが、前回のSame Treeと異なりバイナリツリー1つしかないので、もしツリーがない場合Trueを返す処理を挟んでいるだけです。
isMirror関数の処理はSame Treeに似ていますが、
(左側のツリーの左側と右側のツリーの右側)、(右側のツリーの左側と右側のツリーの左側)の各々が同一かどうかを判定するようにします。
解法2
Iterativeな解法。
せっかくなので前回記事でも取り扱った、deque型を使って書いてみます。
from collections import deque class Solution: def isSymmetric(self, root): if not root: return True deq = deque([(root.left, root.right),]) while deq: t1, t2 = deq.popleft() if not t1 and not t2: continue elif (not t1 or not t2) or (t1.val != t2.val): return False deq.append((t1.left, t2.right)) deq.append((t1.right, t2.left)) return True
以下にSame Treeの時のコードを再掲します。微妙な差異しかないのが分かるかと思います。
from collections import deque class Solution: def isSameTree(self, p, q): def check(p, q): if not p and not q: return True if not q or not p: return False if p.val != q.val: return False return True deq = deque([(p, q),]) while deq: p, q = deq.popleft() if not check(p, q): return False if p: deq.append((p.left, q.left)) deq.append((p.right, q.right)) return True