【LeetCode】101. Symmetric Treeを解く

問題へのリンク

問題概要

二分木rootが与えられたとき，それが対称な二分木であるかどうかをチェックする．

例：

     1
   /   \
  2     2
 / \   / \
3   4 4   3
Input: root = [1,2,2,3,4,4,3]
Output: true

     1
   /   \
  2     2
   \     \
    3     3
Input: root = [1,2,2,null,3,null,3]
Output: false

制約

• ノードの数$[1,100]$
• $-100 \leq Node.val \leq 100$

考えたこと

rootを与えられたとき，二分木が対称となるにはL = root.left，R = root.rightとして

• LとRが鏡写しの関係

を満たす必要がある．

では，鏡写しの関係であることを確かめるにはどうすればよいだろうか？

LとRを詳細に示すと以下のようになる：

     L            R
   /   \        /   \
  A     B      B     A
 / \   / \    / \   / \
C   D E   F  F   E D   C

鏡写しの関係であることを確かめる関数をisMirror(node1,node2)とする．

このときisMirror(L,R)がTrueになるには，

1. $L.val == R.val$
2. isMirror(L.left, R.right) = TrueかつisMirror(L.right, R.left) = True

である必要があると分かる．

そして，isMirror(L.left, R.right) = TrueかつisMirror(L.right, R.left) = Trueとなるには，

1. $L.left.val == R.right.val$
2. isMirror(L.left.left, R.right.right) = TrueかつisMirror(L.left.right, R.right.left) = True
3. $L.right.val == R.left.val$
4. isMirror(L.right.left, R.left.right) = TrueかつisMirror(L.right.right, R.left.left) = True
   ....

というように，再帰的に調べることで鏡写しの関係を確かめられることが分かる．

このとき，再帰関数の終了する条件は部分木L,Rの葉に到達した地点で，

1. node1 is null and node2 is null -> True
2. node1 is null or node2 is null -> False

のようになる．

以上の考えをコードにすると以下のようになる：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def isMirror(t1, t2):
            if t1 is None and t2 is None:
                return True
            if t1 is None or t2 is None:
                return False
            
            if t1.val == t2.val:
                return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)
            else:
                return False
         
        return isMirror(root.left, root.right)