forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsocow.py
More file actions
74 lines (55 loc) ยท 1.85 KB
/
socow.py
File metadata and controls
74 lines (55 loc) ยท 1.85 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
74
"""
๐ 226. Invert Binary Tree
๐ ๋ฌธ์ ์์ฝ
- ์ด์ง ํธ๋ฆฌ๋ฅผ ์ข์ฐ๋ก ๋ค์ง๊ธฐ (๊ฑฐ์ธ์ฒ๋ผ!)
- ๋ชจ๋ ๋
ธ๋์์ ์ผ์ชฝ ์์ โ ์ค๋ฅธ์ชฝ ์์ ๊ตํ
๐ ๋ฌธ์ ์์
์
๋ ฅ: ์ถ๋ ฅ:
4 4
/ \ / \
2 7 โ 7 2
/ \ / \ / \ / \
1 3 6 9 9 6 3 1
๐ฏ ํต์ฌ ์๊ณ ๋ฆฌ์ฆ
- ํจํด: ์ฌ๊ท (DFS) / ๋ฐ๋ณต (BFS)
- ์๊ฐ๋ณต์ก๋: O(n) - ๋ชจ๋ ๋
ธ๋ ๋ฐฉ๋ฌธ
- ๊ณต๊ฐ๋ณต์ก๋: O(h) - h๋ ํธ๋ฆฌ ๋์ด (์ฝ์คํ)
๐ก ํต์ฌ ์์ด๋์ด
1. ํ์ฌ ๋
ธ๋์ ์ผ์ชฝ/์ค๋ฅธ์ชฝ ์์์ swap
2. ์ผ์ชฝ ์๋ธํธ๋ฆฌ ์ฌ๊ท์ ์ผ๋ก ๋ค์ง๊ธฐ
3. ์ค๋ฅธ์ชฝ ์๋ธํธ๋ฆฌ ์ฌ๊ท์ ์ผ๋ก ๋ค์ง๊ธฐ
"""
from typing import Optional
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# ์ฌ๊ท ๋ฐฉ์ (๊ฐ์ฅ ๊ฐ๋จ!)
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
# ์ผ์ชฝ โ ์ค๋ฅธ์ชฝ swap!
root.left, root.right = root.right, root.left
# ์์๋ค๋ ์ฌ๊ท์ ์ผ๋ก ๋ค์ง๊ธฐ
self.invertTree(root.left)
self.invertTree(root.right)
return root
# BFS ๋ฐฉ์ (๋ฐ๋ณต)
class SolutionBFS:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
queue = deque([root])
while queue:
node = queue.popleft()
# swap!
node.left, node.right = node.right, node.left
# ์์๋ค ํ์ ์ถ๊ฐ
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return root