101. Symmetric Tree

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

 

Example 1:

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

Example 2:

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

 

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• -100 <= Node.val <= 100

---

# https://www.acmicpc.net/problem/

'''
1. 아이디어 :
    1) dfs를 이용해서, 양쪽 노드의 값을 비교한다.
2. 시간복잡도 :
    1) O(n)
3. 자료구조 :
    1) dfs
'''


# 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:
        def dfs(lnode, rnode):
            if not lnode and not rnode:
                return True
            if not lnode or not rnode:
                return False
            if lnode.val != rnode.val:
                return False
            return dfs(lnode.left, rnode.right) and dfs(lnode.right, rnode.left)

        return dfs(root.left,root.right)