•
문제 링크 : 
LeetCodeSame 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
stack_p = []
stack_q = []
self.search_tree(p, stack_p)
self.search_tree(q, stack_q)
return stack_p == stack_q
def search_tree(self, node, stack):
if not node:
return
if node.left:
self.search_tree(node.left, stack)
else:
stack.append(None)
if node.right:
self.search_tree(node.right, stack)
else:
stack.append(None)
stack.append(node.val)
Python
복사
•
성공 코드
순회 중 틀린 Node가 나온다면 바로 종료하기 때문에, 훨씬 빠르다.
# 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
# 둘다 None일 경우
if p == None and q == None:
return True
# 둘 중 하나라도 값이 존재하는데, 두 값이 다를 때
if not p or not q or p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
Python
복사