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