Skip to content

Commit 2d73e48

Browse files
author
Chris Wu
committed
no message
1 parent 0f0ce63 commit 2d73e48

3 files changed

Lines changed: 213 additions & 2 deletions

File tree

‎problems/lowest-common-ancestor-of-a-binary-search.py‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
class Solution(object):
2+
def lowestCommonAncestor(self, root, p, q):
3+
def find_ancestors(target):
4+
ancestors = []
5+
curr = root
6+
while curr:
7+
ancestors.append(curr)
8+
9+
if curr is target: break
10+
11+
if target.val>curr.val:
12+
curr = curr.right
13+
else:
14+
curr = curr.left
15+
16+
ancestors.reverse()
17+
return ancestors
18+
19+
def find_lowest_common(a1, a2):
20+
if len(a1)>len(a2):
21+
a2 = set(a2)
22+
for node in a1:
23+
if node in a2:
24+
return node
25+
else:
26+
a1 = set(a1)
27+
for node in a2:
28+
if node in a1:
29+
return node
30+
31+
p_ancestors = find_ancestors(p)
32+
q_ancestors = find_ancestors(q)
33+
return find_lowest_common(p_ancestors, q_ancestors)
34+
"""
35+
The idea is simple
36+
Find all the ancestors of `p` and `q`.
37+
After that, we see if the lowest node exist in both `p_ancestor` and `q_ancestor`.
38+
To make sure we start from the lowest node, we need to start from the larger `p_ancestor` or `q_ancestor`.
39+
40+
Time complexity: O(LogN).
41+
find_ancestors() is O(LogN).
42+
find_lowest_common is O(LogN).
43+
Space complexity is O(N), since `p_ancestors` or `q_ancestors` is carry LogN of nodes.
44+
"""

‎problems/lowest-common-ancestor-of-a-binary-tree.py‎

Lines changed: 132 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,132 @@
1+
class Solution(object):
2+
def lowestCommonAncestor(self, root, p, q):
3+
p_ancestor = []
4+
q_ancestor = []
5+
6+
stack = []
7+
stack.append((root, []))
8+
while stack:
9+
node, path = stack.pop()
10+
if node is p: p_ancestor = path+[p]
11+
if node is q: q_ancestor = path+[q]
12+
if p_ancestor and q_ancestor: break #[0]
13+
if node.left: stack.append((node.left, path+[node]))
14+
if node.right: stack.append((node.right, path+[node]))
15+
16+
if len(p_ancestor)>len(q_ancestor): #[1]
17+
s = set(q_ancestor)
18+
for node in reversed(p_ancestor): #[2]
19+
if node in s: return node #[3]
20+
else: #[1]
21+
s = set(p_ancestor)
22+
for node in reversed(q_ancestor): #[2]
23+
if node in s: return node #[3]
24+
return None
25+
26+
27+
28+
class Solution(object):
29+
def lowestCommonAncestor(self, root, p, q):
30+
def helper(node):
31+
if not node: return False
32+
l, r = helper(node.left), helper(node.right)
33+
curr = node is p or node is q
34+
if (int(l)+int(r)+int(curr) >= 2): self.ans = node
35+
return l or r or curr
36+
37+
self.ans = None
38+
helper(root)
39+
return self.ans
40+
41+
42+
43+
class Solution(object):
44+
def lowestCommonAncestor(self, root, p, q):
45+
stack = []
46+
stack.append(root)
47+
48+
parent = {}
49+
parent[root] = None
50+
51+
while p not in parent or q not in parent:
52+
node = stack.pop()
53+
if node.left:
54+
parent[node.left] = node
55+
stack.append(node.left)
56+
if node.right:
57+
parent[node.right] = node
58+
stack.append(node.right)
59+
60+
p_ancestor = p
61+
q_ancestor = q
62+
p_ancestors = set()
63+
while p_ancestor:
64+
p_ancestors.add(p_ancestor)
65+
p_ancestor = parent[p]
66+
while q_ancestor:
67+
if q_ancestor in p_ancestors: return q_ancestor
68+
q_ancestor = parent[q]
69+
70+
return None
71+
72+
73+
#2020/7/11
74+
class Solution(object):
75+
def lowestCommonAncestor(self, root, p, q):
76+
def find_genealogy():
77+
genealogy = {}
78+
stack = []
79+
stack.append(root)
80+
p_found = q_found = False
81+
while stack:
82+
node = stack.pop()
83+
if node.left:
84+
genealogy[node.left] = node
85+
stack.append(node.left)
86+
if node.right:
87+
genealogy[node.right] = node
88+
stack.append(node.right)
89+
90+
if node is p: p_found = True
91+
if node is q: q_found = True
92+
if p_found and q_found: break
93+
return genealogy
94+
95+
def find_ancestors(target, genealogy):
96+
ancestors = []
97+
curr_node = target
98+
while curr_node:
99+
ancestors.append(curr_node)
100+
curr_node = genealogy[curr_node] if curr_node in genealogy else None
101+
return ancestors
102+
103+
def find_lowest_common(a1, a2):
104+
if len(a1)>len(a2):
105+
a2 = set(a2)
106+
for node in a1:
107+
if node in a2:
108+
return node
109+
else:
110+
a1 = set(a1)
111+
for node in a2:
112+
if node in a1:
113+
return node
114+
115+
genealogy = find_genealogy()
116+
p_ancestors = find_ancestors(p, genealogy)
117+
q_ancestors = find_ancestors(q, genealogy)
118+
return find_lowest_common(p_ancestors, q_ancestors)
119+
120+
"""
121+
The idea is simple
122+
Find all the ancestors of `p` and `q`.
123+
To find ancestors of `p` and `q`, we need to generate a `genealogy`, where we can find the parant of each node. (genealogy[child] = parant)
124+
After that, we see if the lowest node exist in both `p_ancestor` and `q_ancestor`.
125+
To make sure we start from the lowest node, we need to start from the larger `p_ancestor` or `q_ancestor`.
126+
127+
Time complexity: O(N).
128+
find_genealogy() is O(N), because we use DFS to travel all nodes.
129+
find_ancestors() is O(LogN).
130+
find_lowest_common is O(LogN).
131+
Space complexity is O(N), since `genealogy` may carry all the nodes.
132+
"""

‎problems/sum-root-to-leaf-numbers.py‎

Lines changed: 37 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -17,7 +17,42 @@ def sumNumbers(self, root):
1717
stack.append((node.right, total))
1818
return ans
1919

20+
#2020/7/11
21+
class Solution(object):
22+
def sumNumbers(self, root):
23+
if not root: return 0
24+
25+
ans = 0
26+
stack = []
27+
stack.append((root, 0))
28+
29+
while stack:
30+
node, n = stack.pop()
31+
n = n*10+node.val
32+
if not node.left and not node.right: ans+=n
33+
if node.left: stack.append((node.left, n))
34+
if node.right: stack.append((node.right, n))
35+
36+
return ans
37+
2038
"""
2139
Time complexity: O(N), since we use DFS to traverse each node once.
22-
Space complexity: O(NLogN), since each node (at the very bottom), may carry all the digit from its ancestor, LogN.
23-
"""
40+
Space complexity: O(LogN).
41+
Most of the memory we use is in the stack.
42+
tack will at most carry one path (root to leaf), each node containing one digit. O(LogN)
43+
"""
44+
45+
46+
47+
48+
49+
50+
51+
52+
53+
54+
55+
56+
57+
58+

0 commit comments

Comments
 (0)