[LeetCode] 101. Symmetric Tree 풀이 및 코드

문제

이진 트리가 주어질때, 중심을 기준으로 대칭인지를 결과로 리턴하라.

---

풀이

이 문제를 푸는 방법은 재귀(recursively)와 반복(iteratively) 2가지 방법이 있다.

우선 재귀로 푸는 방법을 살펴보자. 보통 Tree 문제를 재귀로 풀때에는 root를 확인하고, 왼쪽 서브트리와 오른쪽 서브트리를 확인하는 방식으로 구현한다. 이 문제도 똑같은 방법으로 해결 가능하다. 단, 주의할 점은 대칭임을 확인하기 위해서는 왼쪽 서브트리와 오른쪽 서브트리를 반대로 비교해야 한다. 즉 두 서브트리의 root가 같은지 확인하고, 왼쪽 서브트리의 left가 오른쪽 서브트리의 right가 같은지, 왼쪽 서브트리의 right이 오른쪽 서브트리의 leftt가 같은지 확인하면 된다.

같은 풀이를 iterative하게도 풀 수 있다. 재귀로 풀었던 것을 큐(Queue)를 이용하여 root부터 더 이상 자식이 없는 leaf까지 순회하면 된다.

---

코드

1. Recursive

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

2. Iterative 

class Solution(object):
    def isSymmetric(self, root):
        queue = [root, root]
        while len(queue) != 0:
            left = queue.pop(0)
            right = queue.pop(0)
            if not left and not right:
                continue
            if not left or not right:
                return False
            else:
                if left.val == right.val:
                    queue.extend([left.left, right.right, left.right, right.left])
                else:
                    return False
        return True

---

리트코드 제출 결과

1. Recursive

2. Iterative

Iterative 방식이 큐를 쓰기 때문에 더 메모리를 많이 쓰는 것(13.7MB > 13.5MB)을 확인할 수 있다.

(일반적으로 Recursive한 방법은 function call을 계속 부르기 때문에 더 느린 것으로 알고 있는데 이 문제에서는 더 빠르다. 혹시 그 이유를 알고 있는 분 계신가요..??)

---

참조

leetcode.com/problems/symmetric-tree/