ほぼ日刊競プロ leetcode　101. Symmetric Tree

101. Symmetric Tree

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

考えたこと

まず初めにinorderでリストに追加していき，逆にした時と一致すれば正解なのでは？と考えた

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
   def isSymmetric(self, root: Optional[TreeNode]) -> bool:
       ans = False
       temp = []
       def help(root,temp):
           if root is not None:
               help(root.left,temp)
               temp.append(root.val)
               help(root.right,temp)
               return temp
           else:
               temp.append(None)
               return temp
       help(root,temp)
       if temp==temp[::-1]:
           print (temp)
           print (temp[::-1])
           return True
       else:
           return False

しかし，反例として[1,2,2,2,null,2]という入力があった時に，左右対象かどうかを判定できない．[1,2,2,null,3,null,3]でもダメ

ゼロから始めるLeetCode Day27「101. Symmetric Tree」
LeetCode】101. Symmetric Treeを解く

いつも通り解を見て納得する．今回は深さ探索で解を求める．
左右のノードを再帰的に見て判定する．根についている左側のノード（ここではt1）についている左側のノードと右側のノード（t2）の右側が等しく，かつt1の右側とt2の左側が等しいければ良いと考え，再帰的に回していく．
どちらかのノードがnullであった場合でも，t1とt2が一致すればTrueを返す．

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
   def isSymmetric(self, root: Optional[TreeNode]) -> bool:
       if root is None:
           return True
       
       def help(t1,t2):
           if t1 is not None and t2 is not None:
               #print (t1)
               #print (t2)
               return t1.val == t2.val and help(t1.left,t2.right) and help(t1.right,t2.left)
           else:
               return t1==t2
       
       return help(root,root)