forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathKwonNayeon.py
More file actions
73 lines (57 loc) ยท 1.92 KB
/
KwonNayeon.py
File metadata and controls
73 lines (57 loc) ยท 1.92 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
"""
Constraints:
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
<Solution 1>
Time Complexity: O(n)
- ๊ฐ ๋
ธ๋๋ฅผ ํ ๋ฒ์ฉ ๋ฐฉ๋ฌธํจ
Space Complexity: O(w)
- w๋ ํธ๋ฆฌ์ ์ต๋ ๋๋น(width)
ํ์ด๋ฐฉ๋ฒ:
1. ํ๋ฅผ ์ฌ์ฉํ BFS(๋๋น ์ฐ์ ํ์)
2. FIFO(First In First Out)๋ก ๋
ธ๋๋ฅผ ์ฒ๋ฆฌํจ
3. ๊ฐ ๋
ธ๋๋ฅผ ๋ฐฉ๋ฌธํ ๋๋ง๋ค:
- ์ผ์ชฝ๊ณผ ์ค๋ฅธ์ชฝ ์์ ๋
ธ๋์ ์์น๋ฅผ ๊ตํ
- ๊ตํ๋ ์์ ๋
ธ๋๋ค์ ํ์ ์ถ๊ฐํ์ฌ ๋ค์ ๋
ธ๋๋ฅผ ์ฒ๋ฆฌํจ
<Solution 2>
Time Complexity: O(n)
- ๊ฐ ๋
ธ๋๋ฅผ ํ ๋ฒ์ฉ ๋ฐฉ๋ฌธํจ
Space Complexity: O(h)
- h๋ ํธ๋ฆฌ์ ๋์ด, ์ฌ๊ท ํธ์ถ ์คํ์ ์ต๋ ๊น์ด
ํ์ด๋ฐฉ๋ฒ:
1. DFS(๊น์ด ์ฐ์ ํ์)์ ์ฌ๊ท๋ฅผ ํ์ฉ
2. ๊ฐ ๋
ธ๋์์:
- ์ผ์ชฝ๊ณผ ์ค๋ฅธ์ชฝ ์์ ๋
ธ๋์ ์์น๋ฅผ ๊ตํ
- ์ฌ๊ท์ ์ผ๋ก ์ผ์ชฝ, ์ค๋ฅธ์ชฝ ์๋ธํธ๋ฆฌ์ ๋ํด ๊ฐ์ ๊ณผ์ ๋ฐ๋ณต
3. Base case: root๊ฐ None์ด๋ฉด None ๋ฐํ
"""
# 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
from collections import deque
# Solution 1 (BFS ํ์ฉ)
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
queue = deque([root])
while queue:
node = queue.popleft()
node.left, node.right = node.right, node.left
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return root
# Solution 2 (DFS์ ์ฌ๊ท ํ์ฉ)
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root