😎

【LeetCode】101. Symmetric Treeを解く

2 min read

問題へのリンク

問題概要

二分木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.leftR = root.rightとして

  • LR鏡写しの関係

を満たす必要がある.

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

LRを詳細に示すと以下のようになる:

     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)

Discussion

ログインするとコメントできます