[LeetCode]Symmetric Tree

https://leetcode.com/problems/symmetric-tree/

Symmetric Tree - LeetCode

 

문제 분석

이진트리가 주어졌을 때 대칭구조를 가지는 트리인지 구하는 문제입니다.

 

처음 시도한 답안

# 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.check_symmetric(root.left, root.right)
        
    
    # 왼쪽 자식과 오른쪽 자식노드가 대칭을 이루는지 확인하는 함수. 재귀로 구현
    def check_symmetric(self, left, right):
        if left is None and right is None:
            return True

        if left is None or right is None:
            return False

        if left.val != right.val:
            return False
		
        # 자식 트리들이 모두 대칭을 이루어야 함.
        return self.check_symmetric(left.right, right.left) and self.check_symmetric(left.left, right.right)

 

접근 방법

1. 루트노드에서부터 내려가면서 왼쪽의 자식노드, 오른쪽의 자식 노드가 서로 대칭인지 검사합니다.
2. 왼, 오른쪽의 트리가 모두 없다면 대칭을 이룹니다.
3. 왼, 오른쪽의 트리가 한 곳만 존재한다면 대칭을 이루지 않습니다.
4. 왼, 오른쪽의 트리가 존재하는데 값이 다르다면 대칭을 이루지 않습니다.
5. 아래의 자식 노드들도 대칭을 이루는지 확인하기 위해 (왼쪽 자식의 오른쪽 노드, 오른쪽 자식의 왼쪽 노드), (왼쪽 자식의 왼쪽 노드, 오른쪽 자식의 오른쪽 노드) 두개가 모두 대칭을 이루는지 재귀적으로 확인합니다.

이 문제를 풀기 위해서는 중요한 포인트 두가지가 있습니다.

• 트리가 대칭 구조가 되기 위해서는 (왼쪽 자식의 오른쪽 노드, 오른쪽 자식의 왼쪽 노드) 의 값이 같고, (왼쪽 자식의 왼쪽 노드, 오른쪽 자식의 오른쪽 노드) 또한 값이 같아야 합니다.
• 왼쪽과 오른쪽의 트리를 동시에 탐색하기 위해서 left, right 노드 2개를 이용하여 재귀적으로 탐색합니다.