•
•
문제 설명 : 주어진 트리가 Root 노드를 기준으로 대칭인지 확인
•
풀이 방법
◦
만약 대칭이라면 어떨지 먼저 생각해보았다.
▪
우선 왼쪽과 오른쪽을 따로 순회하여 결과가 대칭인지 확인하는 느낌이었다.
▪
Root의 왼쪽 트리는 [좌 → 중앙 → 우] 로 DFS 탐색
▪
Root의 오른쪽 트리는 [우 → 중앙 → 좌] 로 DFS 탐색
▪
만약 대칭이라면, [Root의 왼쪽 트리 탐색 결과] == [Root의 우쪽 트리 탐색 결과] 일 것이다.
▪
확실한 비교를 위해, 하위 노드가 없는 경우는 None 값을 넣어주었다.
•
시간복잡도 :
•
성공 코드
# 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:
left_stack = []
right_stack = []
# Root 노드만 존재하는 경우
if root.left == None and root.right == None:
return True
# Root 노드의 좌/우 노드가 하나라도 존재하지 않는 경우
elif root.left == None or root.right == None:
return False
# 좌측 트리의 정보를 확인
self.search_left_first(root.right, left_stack)
# 우측 트리의 정보를 확인
self.search_right_first(root.left, right_stack)
# 탐색을 대칭으로 진행한 결과가 동일한지 확인
return left_stack == right_stack
# 좌 -> 중앙 -> 우 순서로 탐색
def search_left_first(self, node, stack):
if node.left:
self.search_left_first(node.left, stack)
stack.append(node.val)
else:
stack.append(None)
stack.append(node.val)
if node.right:
self.search_left_first(node.right, stack)
stack.append(node.val)
else:
stack.append(None)
# 우 -> 중앙 -> 좌 순서로 탐색
def search_right_first(self, node, stack):
if node.right:
self.search_right_first(node.right, stack)
stack.append(node.val)
else:
stack.append(None)
stack.append(node.val)
if node.left:
self.search_right_first(node.left, stack)
stack.append(node.val)
else:
stack.append(None)
Python
복사