# [Leetcode]100. Same Tree

limelimejiwon·2022년 3월 21일
0

목록 보기
19/67

## 📄 Description

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.

### Example 1:

Input: p = [1,2,3], q = [1,2,3]
Output: true

### Example 2:

Input: p = [1,2], q = [1,null,2]
Output: false

### Example 3:

Input: p = [1,2,1], q = [1,1,2]
Output: false

## 💻 My Submission - BFS

class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
queue=[]
queue.append((p,q))

while queue:
p1,q1=queue.pop(0)
if not p1 and not q1:
continue
elif None in [p1,q1]:
return False
else:
if p1.val!=q1.val:
return False
queue.append((p1.left,q1.left))
queue.append((p1.right,q1.right))
return True

## Other Solutions (1) DFS using stack

class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
stack=[]
stack.append((p,q))

while stack:
p1,q1=stack.pop()
if not p1 and not q1:
continue
elif None in [p1,q1]:
return False
else:
if p1.val!=q1.val:
return False
stack.append((p1.right,q1.right))
stack.append((p1.left,q1.left))
return True

## Other Solutions (2) Recursion

	def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if not p and not q:
return True
if p and q and p.val==q.val:
return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
return False

## 💡 What I learned

#### 1. How to check if one of two is None

if None in [p1,q1]:

#### 2. How DFS using stack and BFS using queue is different?

• the order you add to stack/queue
• whether you pop off the left(pop(0)) or the rightmost(pop()) element.

(1) DFS

• pop off the left element
• add to stack right node, then left node
stack.pop()
...
stack.append((p1.right, q1.right))
stack.append((p1.left, q1.right))

(2) BFS

• pop off the rightmost element
• add to queue left node, then right node
queue.pop(0)
...
queue.append((p1.left, q1.right))
queue.append((p1.right, q1.right))