-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbinaryTreePaths.py
More file actions
65 lines (45 loc) · 1.47 KB
/
binaryTreePaths.py
File metadata and controls
65 lines (45 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
# 257. 二叉树的所有路径
def binaryTreePaths1(root):
"""
DFS
达到节点，将节点值加入到path字符串中
如果到达叶子节点时，得到一个完整路径，加入到路径列表中，深度搜索结束。
如果未到达叶子节点，则继续向下搜索。
"""
def construct_paths(root, path):
if root:
path += str(root.val)
if not root.left and not root.right:
paths.append(path)
else:
path += "->"
construct_paths(root.left, path)
construct_paths(root.right, path)
paths = []
construct_paths(root, "")
return paths
def binaryTreePaths2(root):
"""
BFS
使用到两个队列
队列一: 存储 BFS 遍历时的节点
队列二: 存储 队列一中从根节点到指定节点的路径
"""
paths = []
if not root:
return paths
node_queue = [root]
path_queue = [str(root.val)]
while node_queue:
path = ""
node = node_queue.pop(0)
node_path = path_queue.pop(0)
if not node.left and not node.right:
paths.append(path)
if not node.left:
node_queue.append(node.left)
path_queue.append(node_path + "->" + str(node.left.val))
if not node.right:
node_queue.append(node.right)
path_queue.append(node_path + "->" + str(node.right.val))
return paths