-
Notifications
You must be signed in to change notification settings - Fork 0
/
pathSumIII.py
148 lines (119 loc) · 3.49 KB
/
pathSumIII.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
140
141
142
143
144
145
146
147
148
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
@author: zenithude.
"""
from collections import defaultdict
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = None
self.right = None
def __repr__(self):
return 'TreeNode({})'.format(self.val)
def deserialize(string):
if string == '{}':
return None
nodes = [None if val == 'null' else TreeNode(int(val)) for val in
string.strip('[]{}').split(',')]
kids = nodes[::-1]
root = kids.pop()
for node in nodes:
if node:
if kids: node.left = kids.pop()
if kids: node.right = kids.pop()
return root
def insert(temp, data):
que = []
que.append(temp)
while (len(que)):
temp = que[0]
que.pop(0)
if (not temp.left):
if data is not None:
temp.left = TreeNode(data)
else:
temp.left = TreeNode(0)
break
else:
que.append(temp.left)
if (not temp.right):
if data is not None:
temp.right = TreeNode(data)
else:
temp.right = TreeNode(0)
break
else:
que.append(temp.right)
def make_tree(elements):
Tree = TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
def inorderTraversal(root):
"""
Left -> Root -> Right
:param root: TreeNode()
:return: List[int]
"""
res = []
if root:
res = inorderTraversal(root.left)
res.append(root.val)
res = res + inorderTraversal(root.right)
return res
def postorderTraversal(root):
"""
Left -> Right -> Root
:param root: TreeNode()
:return: List[int]
"""
res = []
if root:
res = postorderTraversal(root.left)
res = res + postorderTraversal(root.right)
res.append(root.val)
return res
def preorderTraversal(root):
"""
Root -> Left ->Right
:param root: TreeNode()
:return: List[int]
"""
res = []
if root:
res.append(root.val)
res = res + preorderTraversal(root.left)
res = res + preorderTraversal(root.right)
return res
def search(root, key):
# Base Cases: root is null or key is present at root
if root is None or root.val == key:
return root
# Key is greater than root's key
if root.val < key:
return search(root.right, key)
# Key is smaller than root's key
return search(root.left, key)
class Solution:
def cumSum(self, root):
self.n += 1
for child in filter(None, [root.left, root.right]):
child.val += root.val
self.cumSum(child)
def dfs(self, root, sum):
if not root: return None
self.count[root.val + sum] += 1
self.result += self.count[root.val]
self.dfs(root.left, sum)
self.dfs(root.right, sum)
self.count[root.val + sum] -= 1
def pathSum(self, root, sum):
if not root: return 0
self.n, self.result, self.count = 0, 0, defaultdict(int)
self.cumSum(root)
self.count[sum] = 1
self.dfs(root, sum)
return self.result - self.n * (sum == 0)
tree = make_tree([4, 2, 7, 1, 3])
obj = Solution()