forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathhi-rachel.py
More file actions
50 lines (44 loc) ยท 1.47 KB
/
hi-rachel.py
File metadata and controls
50 lines (44 loc) ยท 1.47 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
from typing import Optional
# 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
"""
์ฌ๊ท ํ์
TC: O(N), ์ ํธ๋ฆฌ์ ๊ฐ ๋
ธ๋๋ฅผ ์๋๋ก ์ฌ๊ทํจ์๋ฅผ ๋ฑ 1๋ฒ์ฉ๋ง ํธ์ถํ๊ธฐ ๋๋ฌธ
SC: O(N), ๊ณต๊ฐ๋ณต์ก๋ = ์ฝ์คํ์ ์ต๋ ๋์ด(๋
ธ๋์ ์)
"""
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
# ๋ ๋ค null์ด๋ฉด True ๋ฐํ
if not p and not q:
return True
# ๋ ์ค ํ๋๋ฉด null์ด๋ฉด False ๋ฐํ
if not p or not q:
return False
# val์ด ์๋ก ๋ค๋ฅด๋ฉด ํ์ ์ค๋จ, False ๋ฐํ
if p.val != q.val:
return False
# ํ์ฌ node์ val์ด ๊ฐ๋ค๋ฉด, ์ข์ฐ์ธก ์์ ํธ๋ฆฌ๋ ๊ฐ์์ง ํ์ธ -> ์ฌ๊ท ํธ์ถ
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
"""
์คํ ํ์ด
TC: O(N)
SC: O(N)
"""
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
stack = [(p, q)]
while stack:
p, q = stack.pop()
if not p and not q:
continue
if not p or not q:
return False
if p.val != q.val:
return False
stack.append((p.left, q.left))
stack.append((p.right, q.right))
return True