LeetCode: 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

 

Follow up: Could you solve it both recursively and iteratively?

 

 

이 문제는 root만을 기준으로 좌우가 대칭인지 살펴보는 문제이다. 

 

문제푸는 방식은 다음과 같다. 

 

root를 기준으로 오른쪽과 왼쪽 노드가 존재하지 않는다면 True를 반환한다. 

root가 없어도 True를 반환한다. 

 

이후 값이 같고 재귀의 방식으로 오른쪽 노드의 오른쪽과 왼쪽 노드의 왼쪽, 왼쪽노드의 오른쪽과 오른쪽 노드의 오른쪽 노드를 같은 함수의 parameter로 집어 넣는다.  이 값이 return값이 된다. 

(값이 같은지 확인 + 대칭인지 확인) 

 

이 과정을 반복하면 root를 기준으로 트리가 대칭인지 확인할 수 있게 된다!

 

생각하는데 시간이 굉장히 오래걸렸다.. 이런.. 

 

 

---

구현코드

# 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 not t1 and not t2:
                return True
            if not t1 or not t2:
                return False
            return (t1.val == t2.val and
                    isMirror(t1.left, t2.right) and
                    isMirror(t1.right, t2.left))
        
        return isMirror(root.left, root.right) if root else True