[LeetCode] #101. Symmetric Tree (Python/파이썬)

📖Problem: 101. Symmetric Tree

이진 트리가 주어졌을 때, 대칭이면 True를 아니면 False를 반환한다.

 

예제

---

🔍Institution

1. 트리 문제이고, 트리를 탐색해야 한다. 즉, DFS나 BFS로 풀어야한다.
2. 이때, DFS로 풀어야 하나, BFS로 풀어야 할까?
   • 예제를 보면 한층한층 비교하는 BFS가 맞을 것 같은데,, 출력예시 보면 DFS처럼 재귀호출하는게 좋을 것 같다. 그래서 헷갈렸다.
   • 하지만, 어떤 방법으로 풀든 상관없다.
3. BFS로 풀면 큐를 이용해야 하는데 큐를 사용하는 건 아직 미숙해서 DFS로 결정!

 

그렇다면 DFS로 어떻게 풀 것인가?!

• 이진트리가 대칭인지 확인하려면 왼쪽 부분 트리와 오른쪽 부분 트리를 비교해야 한다.
• root의 왼쪽 부분(root.left)와 오른쪽 부분(root.right)을 따로 재귀호출하여 각 부분에서 또 다시 왼쪽과 오른쪽을 비교한다. 대칭이면 계속 깊이 탐색을 하고, 그렇지 않으면 바로 false를 return한다.

---

🔍Approach

Treenode의 root를 print했을 때는 아래와 같이 출력된다.

print(root)

TreeNode{val: 1, left: TreeNode{val: 2, left: TreeNode{val: 3, left: None, right: None}, right: TreeNode{val: 4, left: None, right: None}}, right: TreeNode{val: 2, left: TreeNode{val: 4, left: None, right: None}, right: TreeNode{val: 3, left: None, right: None}}}

이를 참고하여 val, left, right를 쓰도록 한다.

 

Flow

1. 대칭인지 아닌지 확인하는 mirror함수를 호출한다.
2. mirror함수는 왼쪽 부분 트리(root.left)와 오른쪽 부분 트리(root.right)를 매개변수로 전달 받아 실행된다.
   1. 만약 트리의 왼쪽 부분(left_tree)와 오른쪽 부분(right_tree)이 둘 다 null이라면 (즉, 둘 다 None이라면) 트리의 가장 밑 부분임을 의미한다. 따라서, 마지막이 올 때까지도 중간에 반환 없이 계속 왔으므로, 대칭임을 의미한다. 따라서 True를 반환한다.
   2. left_tree와 right_tree둘 중 하나가 Null이라면, 트리가 비대칭임을 의미한다. 따라서, False를 반환한다.
   3. left_tree와 right_tree의 value값(left_tree.val, right_tree.val)이 같은지 다른지도 비교해야 한다.
      • 만약 다를 경우, 대칭이 아니므로 False를 반환한다.
      • 같을 경우, 그 아래 노드도 대칭인지 아닌지 판단해야 하므로 반환없이 계속 recursion을 진행한다.
   4. 즉, 정리하면 left_tree 와 right_tree둘 다 Null이라면 마지막 부분이므로 True를 return하고 둘 중 하나만 Null이거나 각 val의 값이 다르다면 False를 return한다.
   5. (반환이 안 되었을 경우에는 계속해서 깊이 탐색을 진행해야 한다.) 트리 왼쪽 부분의 왼쪽(left_tree.left)과, 트리 오른쪽 부분의 오른쪽(right_tree.right)을 호출하고 그 다음에는 트리 왼쪽 부분의 오른쪽과 트리 오른쪽 부분의 왼쪽을 호출한다. (이 말이 헷갈린다면 아래 그림을 참고하도록 하자!)

같은 색끼리 대칭이 되어야 한다. 그러려면 한 번은 left_tree의 왼쪽과 right_tree의 오른쪽을 비교하고 또 다른 한 번은 left_tree의 오른쪽과 right_tree의 왼쪽을 비교해야 한다.

🚩My submission

# 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:
        return self.mirror(root.left, root.right)

    def mirror(self, left_tree, right_tree):
        if left_tree is None and right_tree is None:
            return True

        if left_tree is None or right_tree is None:
            return False

        if left_tree.val != right_tree.val:
            return False   


        a = self.mirror(left_tree.left, right_tree.right)
        b = self.mirror(left_tree.right, right_tree.left)

        return a and b

 

• Time complexity: O(n)
  • 여기서 n은 이진 트리의 노드 수이다.
  • 트리가 대칭이라면 각 노드마다 한번씩 체크한다.
• Space complexity: O(h)
  • 여기서 h는 이진 트리의 높이다.
  • 최악의 경우, 트리는 완전한 불균형(completely unbalnced)이될 수도 있고, 재귀나 스택은 트리의 높이만큼 깊게 들어갈 수도 있다.

 

🚩Others submission

DFS

• 가장 높은 조회수와 추천수를 받은 답안

class Solution(object):
    def isMirror(self, left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        return left.val == right.val and self.isMirror(left.left, right.right) and self.isMirror(left.right, right.left)

    def isSymmetric(self, root):
        if not root:
            return True
        return self.isMirror(root.left, root.right)

• 정말 깔끔하다! 나는 따로 변수를 만들어서 return했는데 굳이 그럴 필요 없이 바로 return해도 된다.

BFS (Queue)

def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack = [root]
        res = []
        while stack:
            node = stack.pop()
            if node:
                stack.append(node.right)
                stack.append(node)
                stack.append(node.left)
            else:
                if stack:
                    node = stack.pop()
                    res.append(node.val)

---

💡TIL

• 트리 문제는 복잡하고 헷갈려서 나도 모르게 자꾸 피하게 되는 유형인데, 은지덕에 유형 편식 없이 그나마 풀고 있는 것 같다. (은지가 없었다면, 트리를 아예 접근도 못했을 것..ㅜㅜ) 지난번처럼 완벽하게 이해가 되는데까지는 시간이 좀 걸렸다.
• val, left, right값을 체크하는 게 언제 체크하느냐에 따라 코드 실행이 갈린다. 내가 설정한 조건문을 완벽하게 이해할 필요가 있는데, 나는 조건문을 생각나는대로 작성했고 논리적으로 나열하지 못했다.
• 다음부터는 재귀로 부를 때, 어떤 순서로 불러서 비교해야 할지 조금 더 명확히 이해한 뒤에 작성해야겠다.
• 또 매번 내 시간복잡도와 공간복잡도를 계산하는데 이번에는 내가 계산한게 틀렸다. 다른 사람이 적어놓은 답을 본 이후에, 자료구조시간에 이진트리 시간복잡도와 공간복잡도에 대해 배웠던 게 생각이 났다. 이렇게 다시 리마인드한다~