# Leetcode :: Same Tree

wisepineยท2021๋ 5์ 25์ผ
0

## ์๊ณ ๋ฆฌ์ฆ

๋ชฉ๋ก ๋ณด๊ธฐ
98/121

### Problem

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

### Guess

• ๋ ํธ๋ฆฌ์ ๋ชจ๋  ๋ธ๋๊ฐ ๋์ผํ์ง๋ฅผ ๋ฌป๋ ๋ฌธ์ ๋ค.

• ๋น์ ํ ์๋ฃ๊ตฌ์กฐ๊ธฐ ๋๋ฌธ์ ๋จ์ linear ํ์์ด ๋ถ๊ฐํ๋ค.

• dfs, bfs ๋ชจ๋ ์ ์ฉํด๋ณด์.

### Sol 1. DFS (Recursion)

# 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: TreeNode, q: TreeNode) -> bool:
if not p and not q:
return True
if not p or not q:
return False
if p.val != q.val:
return False

return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

### Sol 2. BFS (Queue)

from collections import deque

class Solution:
def isSameNode(self, p,q):
if not p and not q:
return True
if not p or not q:
return False
if p.val != q.val:
return False

return True

def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
dq = deque([(p, q)])

while dq:
p,q = dq.popleft()

if not self.isSameNode(p,q):
return False

if p:
dq.append((p.left, q.left))
dq.append((p.right, q.right))

return True
๋ฐฐ์ด๊ฑฐ ์์นด์ด๋นํ๋ ๊ณณ