LeetCode 101(Symmetric Tree, Python)

1. 문제 링크

• Symmetric Tree - LeetCode

Symmetric Tree - LeetCode

2. 문제 설명

• 주어진 이진 트리가 가운데에 대하여 좌우 대칭인지 판단하는 문제
• True인 예시

        1
       / \
      2   2
     / \ / \
    3  4 4  3

3. 처음 풀이

• 전위 순회를 하면 루트 →  왼쪽 서브트리 → 오른쪽 서브트리 순으로 방문하는 것이 기본
• 그런데 이를 바꾸어 루트 →  오른쪽 서브트리 → 왼쪽 서브트리 순으로 방문했을 때, 좌우 대칭인 트리라면 그 결과가 같다는 것을 이용하는 아이디어

# 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 order(root,dir = 'left'):
            result = []
            if not root:
                return [None]
            elif dir == 'left': #일반적인 전위 순회
                result.append(root.val) #루트 노드
                result += order(root.left,'left') #왼쪽 서브트리
                result += order(root.right,'left') #오른쪽 서브트리
                return result
            elif dir == 'right': #방향 바뀐 전위 순회
                result.append(root.val) #루트 노드
                result += order(root.right,'right') #오른쪽 서브트리
                result += order(root.left,'right') #왼쪽 서브트리
                return result

        return order(root,'left') == order(root,'right') #두 순회의 결과가 같은 지 확인

4. 다른 풀이

• 재귀로 도무지 생각이 안 났었는데 이렇게 재귀 함수로 해결할 수도 있음
• t1, t2가 모두 None이면 대칭이므로 True
• 그렇지 않다면 t1, t2의 val은 같아야하며, t1 왼쪽 서브트리는 t2 오른쪽 서브트리와 대칭, t1 오른쪽 서브트리는 t2 왼쪽 서브트리와 대칭이어야함을 이용. 

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

5. 배운 점

• 함수에 같은 변수를 두 개의 인수에 넣을 생각은 하지 못하였다. 
• 트리 구조에서는 재귀함수를 적극적으로 사용하자.