-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathbinary_tree_paths.py
More file actions
58 lines (44 loc) ยท 1.68 KB
/
binary_tree_paths.py
File metadata and controls
58 lines (44 loc) ยท 1.68 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
# 257. Binary Tree Paths
# https://leetcode.com/problems/binary-tree-paths/
from typing import List
from copy import copy
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# binary tree ์์ ๋ชจ๋ leaf ๋
ธ๋๋ก ๋ค๋ค๋ฅด๋ ์์๋ค์ val ๊ฐ์ด '->' ๊ธฐํธ๋ฅผ ํตํด ์ด์ด์ ธ์
# ๋ฆฌ์คํธ๋ก ์ถ๋ ฅํด์ผ ํ๋ ๋ฌธ์ ๋ค.
def helper(self, node, p, r):
if node is None:
return
# ํ์ฌ ๋
ธ๋์ ๊ฐ์ ๋ฃ๋๋ค.
p.append(str(node.val))
# ์์ ๋
ธ๋๊ฐ ์์ผ๋ฉด leaf ๋
ธ๋๋ค.
# ์ฌํ๊น์ง ์ถ์ ํ๋ ๊ฒฐ๊ณผ ๊ฐ path list ๋ฅผ join ํด์ ๊ฒฐ๊ณผ ๊ฐ r์ ๋ฃ๋๋ค.
# ์ต์ข
๊ฒฐ๊ณผ ๊ฐ์ด ๋๋ค.
if node.left is None and node.right is None:
r.append("->".join(p))
return
# ๊ฐ ์์ ๋
ธ๋๋ฅผ ์ํํ๋ค.
# ์ด ๋ ๊ธฐ์กด path list์ ๋ค๋ฅธ path list์ด๋ฏ๋ก copy ํจ์๋ฅผ ์จ์
# object copy ๋ฅผ ํผํ๋ค.
if node.left is not None:
p1 = copy(p)
self.helper(node.left, p1, r)
if node.right is not None:
p2 = copy(p)
self.helper(node.right, p2, r)
return
def binaryTreePaths(self, root: TreeNode) -> List[str]:
if root is None:
return []
if root.left is None and root.right is None:
return [str(root.val)]
res = []
# ์ฌ๊ท๋ก ๊ฐ ๋
ธ๋๋ฅผ ๋ชจ๋ ํ์ํ๋ค.
# ๊ฐ arguments ๋ ๋
ธ๋, ์ฌํ๊น์ง ์งํํ๋ ์์, ๊ฒฐ๊ณผ ๊ฐ ์ด๋ค.
self.helper(root, [], res)
return res