-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathhasPathSum.py
139 lines (118 loc) · 4.04 KB
/
hasPathSum.py
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#!/usr/bin/env python
# -*- encoding: utf-8 -*-
'''
@File : hasPathSum.py
@Time : 2024/10/11 22:39:31
@Author : Zihao Zheng
@Email : [email protected]
'''
def traversal( cur, path, result):
path.append(cur.val) # 中
if not cur.left and not cur.right: # 到达叶子节点
sPath = '->'.join(map(str, path))
result.append(sPath)
return
if cur.left: # 左
traversal(cur.left, path, result)
path.pop() # 回溯
if cur.right: # 右
traversal(cur.right, path, result)
path.pop() # 回溯
def binaryTreePaths( root):
result = []
path = []
if not root:
return result
traversal(root, path, result)
return result
def binaryTreePaths2( root): #前序遍历
node_stack,path_stack,result=[root],[str(root.val)],[]
while node_stack:
cur_node=node_stack.pop()
cur_path=path_stack.pop()
if (cur_node.left is None) and (cur_node.right is None):#not （cur_node.left or cur_node.leftcur_node.right）
result.append(cur_path)
if cur_node.right:
node_stack.append(cur_node.right)
path_stack.append(cur_path+'->'+str(cur_node.right.val))
if cur_node.left:
node_stack.append(cur_node.left)
path_stack.append(cur_path+'->'+str(cur_node.left.val))
return result
def hasSumpath(root,sum):
if not root:
return False
node_stack,path_stack=[root],[root.val]
while node_stack:
cur_node=node_stack.pop()
cur_sum=path_stack.pop()
if (cur_node.left is None) and (cur_node.right is None) and cur_sum==sum:#not （cur_node.left or cur_node.leftcur_node.right）
return True
if cur_node.right:
node_stack.append(cur_node.right)
path_stack.append(cur_sum+cur_node.right.val)
if cur_node.left:
node_stack.append(cur_node.left)
path_stack.append(cur_sum+cur_node.left.val)
return False
def hasPathSum(root, sum: int) -> bool:
if not root:
return False
# 此时栈里要放的是pair<节点指针，路径数值>
st = [(root, root.val)]
while st:
node, path_sum = st.pop()
# 如果该节点是叶子节点了，同时该节点的路径数值等于sum，那么就返回true
if not node.left and not node.right and path_sum == sum:
return True
# 右节点，压进去一个节点的时候，将该节点的路径数值也记录下来
if node.right:
st.append((node.right, path_sum + node.right.val))
# 左节点，压进去一个节点的时候，将该节点的路径数值也记录下来
if node.left:
st.append((node.left, path_sum + node.left.val))
return False
def traversal( cur, path, result,value):
path.append(cur.val) # 中
if not cur.left and not cur.right and value==0: # 到达叶子节点
sPath = '->'.join(map(str, path))
result.append(sPath)
return True
if cur.left: # 左
traversal(cur.left, path,result,value-cur.left.val)
path.pop() # 回溯
if cur.right: # 右
traversal(cur.right, path,result,value-cur.right.val)
path.pop() # 回溯
return False
def hasSumpath2(root,sum):
result = []
path = []
if not root:
return False
traversal(root,path,result,sum-root.val)
return result
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
Node1=TreeNode(val=5)
Node2=TreeNode(val=4)
Node3=TreeNode(val=8)
Node4=TreeNode(val=11)
Node5=TreeNode(val=13)
Node6=TreeNode(val=4)
Node7=TreeNode(val=7)
Node8=TreeNode(val=2)
Node9=TreeNode(val=5)
Node10=TreeNode(val=1)
Node1.left=Node2
Node1.right=Node3
Node2.left=Node4
Node3.left=Node5
Node3.right=Node6
Node4.left=Node7
Node4.right=Node8
Node6.left=Node9
Node6.right=Node10