Iterative로 꼭 풀어볼 것!!! - DFS에 대한 Iterative 푸는 것이 중요
방법 1
Queue 이용한 BFS
3가지 case로 나눌 것 (양쪽이 다 None / 한쪽만 None / 둘 다 값이 있는 경우)
class Solution(object):
def isSameTree(self, p, q):
queue = [(p, q)]
while queue:
node1, node2 = queue.pop(0)
if not node1 and not node2:
continue
elif None in [node1, node2]:
return False
else:
if node1.val != node2.val:
return False
queue.append((node1.left, node2.left))
queue.append((node1.right, node2.right))
return True
방법 2
Recursive하게 짠 것
빠져나가는 조건 명확히 찾을 것
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def isSameTree(self, p, q):
if not p or not q :
return p == q
else :
return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
class Solution(object): def isSameTree(self, p, q): if not p or not q : return p == q else : return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)