Skip to content

Commit a699943

Browse files
melody-limelody-li
authored
Merge pull request algorithm004-01#375 from KarsonWu/master
196-Week 02
2 parents ea2e889 + 205fc3c commit a699943

File tree

10 files changed

+82
-10
lines changed

10 files changed

+82
-10
lines changed

‎Week 02/id_196/LeetCode_105_196.py‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
class Solution:
2+
def buildTree(self, preorder: [int], inorder: [int]):
3+
if not inorder: return
4+
root = TreeNode(preorder.pop(0))
5+
i = inorder.index(root.val)
6+
root.left = self.buildTree(preorder, inorder[:i])
7+
root.right = self.buildTree(preorder, inorder[i+1:])
8+
return root
9+

‎Week 02/id_196/LeetCode_144_196.py‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
class Solution(object):
2+
def preorderTraversal(self, root):
3+
if root is None:
4+
return []
5+
6+
stack, output = [root, ], []
7+
8+
while stack:
9+
root = stack.pop()
10+
if root is not None:
11+
output.append(root.val)
12+
if root.right is not None:
13+
stack.append(root.right)
14+
if root.left is not None:
15+
stack.append(root.left)
16+
17+
return output
18+
19+

‎Week 02/id_196/LeetCode_236_196.py‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
class Solution:
2+
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
3+
dic = {root:None}
4+
def dfs(node):
5+
if node:
6+
if node.left:
7+
dic[node.left] = node
8+
if node.right:
9+
dic[node.right] = node
10+
dfs(node.left)
11+
dfs(node.right)
12+
dfs(root)
13+
l1, l2 = p, q
14+
while(l1!=l2):
15+
l1 = dic.get(l1, q)
16+
l2 = dic.get(l2, p)
17+
return l1
18+

‎Week 02/id_196/LeetCode_242_196.py‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
def isAnagram(self, s: str, t: str):
2+
result = True
3+
set_tmp = set(s)
4+
if set_tmp == set(t):
5+
for i in set_tmp:
6+
result = result and (s.count(i) == t.count(i))
7+
else:
8+
result = False
9+
return (result)
10+

‎Week 02/id_196/LeetCode_49_196.py‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
class Solution:
2+
def groupAnagrams(strs):
3+
ans = collections.defaultdict(list)
4+
for s in strs:
5+
count = [0] * 26
6+
for c in s:
7+
count[ord(c) - ord('a')] += 1
8+
ans[tuple(count)].append(s)
9+
return ans.values()
10+

‎Week 02/id_196/LeetCode_94_196.py‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
class Solution:
2+
def inorderTraversal(self, root: TreeNode):
3+
WHITE, GRAY = 0, 1
4+
res = []
5+
stack = [(WHITE, root)]
6+
while stack:
7+
color, node = stack.pop()
8+
if node is None: continue
9+
if color == WHITE:
10+
stack.append((WHITE, node.right))
11+
stack.append((GRAY, node))
12+
stack.append((WHITE, node.left))
13+
else:
14+
res.append(node.val)
15+
return res
16+

‎Week 预习周/id_196/数据结构.png‎

77.3 KB
Loading

‎Week 预习周/id_196/数据结构.url‎

Lines changed: 0 additions & 5 deletions
This file was deleted.

‎Week 预习周/id_196/算法.png‎

45.1 KB
Loading

‎Week 预习周/id_196/算法.url‎

Lines changed: 0 additions & 5 deletions
This file was deleted.

0 commit comments

Comments
 (0)