Skip to content

Commit f5ce7be

Browse files
Ernestkeon
Ernest
authored and
keon
committed
Fix some bug (keon#366)
* Fix bug: explicity compare with None. * Unify node class * Hide slower code. * Update * Only test when file is main * Remove unnecessary code. * Rename and hide implementations. * Fix flake8 * Fix error. * Fix error. * Create __init__.py * Fix error.
1 parent d31ec0a commit f5ce7be

21 files changed

+143
-158
lines changed

‎algorithms/matrix/__init__.py‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+

‎algorithms/tree/bin_tree_to_list.py‎

Lines changed: 4 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,5 @@
1-
class Node():
2-
def __init__(self, val = 0):
3-
self.val = val
4-
self.left = None
5-
self.right = None
1+
from tree.tree import TreeNode
2+
63

74
def bin_tree_to_list(root):
85
"""
@@ -15,6 +12,7 @@ def bin_tree_to_list(root):
1512
root = root.left
1613
return root
1714

15+
1816
def bin_tree_to_list_util(root):
1917
if not root:
2018
return root
@@ -32,18 +30,8 @@ def bin_tree_to_list_util(root):
3230
root.right = right
3331
return root
3432

33+
3534
def print_tree(root):
3635
while root:
3736
print(root.val)
3837
root = root.right
39-
40-
tree = Node(10)
41-
tree.left = Node(12)
42-
tree.right = Node(15)
43-
tree.left.left = Node(25)
44-
tree.left.left.right = Node(100)
45-
tree.left.right = Node(30)
46-
tree.right.left = Node(36)
47-
48-
head = bin_tree_to_list(tree)
49-
print_tree(head)

‎algorithms/tree/binary_tree_paths.py‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,13 @@
11
def binary_tree_paths(root):
22
res = []
3-
if not root:
3+
if root is None:
44
return res
55
dfs(res, root, str(root.val))
66
return res
77

8+
89
def dfs(res, root, cur):
9-
if not root.left and not root.right:
10+
if root.left is None and root.right is None:
1011
res.append(cur)
1112
if root.left:
1213
dfs(res, root.left, cur+'->'+str(root.left.val))

‎algorithms/tree/deepest_left.py‎

Lines changed: 16 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -12,18 +12,15 @@
1212
# 7
1313
# should return 4.
1414

15+
from tree.tree import TreeNode
1516

16-
class Node:
17-
def __init__(self, val = None):
18-
self.left = None
19-
self.right = None
20-
self.val = val
2117

2218
class DeepestLeft:
2319
def __init__(self):
2420
self.depth = 0
2521
self.Node = None
2622

23+
2724
def find_deepest_left(root, is_left, depth, res):
2825
if not root:
2926
return
@@ -33,15 +30,17 @@ def find_deepest_left(root, is_left, depth, res):
3330
find_deepest_left(root.left, True, depth + 1, res)
3431
find_deepest_left(root.right, False, depth + 1, res)
3532

36-
root = Node(1)
37-
root.left = Node(2)
38-
root.right = Node(3)
39-
root.left.left = Node(4)
40-
root.left.right = Node(5)
41-
root.right.right = Node(6)
42-
root.right.right.right = Node(7)
43-
44-
res = DeepestLeft()
45-
find_deepest_left(root, True, 1, res)
46-
if res.Node:
47-
print(res.Node.val)
33+
34+
if __name__ == '__main__':
35+
root = TreeNode(1)
36+
root.left = TreeNode(2)
37+
root.right = TreeNode(3)
38+
root.left.left = TreeNode(4)
39+
root.left.right = TreeNode(5)
40+
root.right.right = TreeNode(6)
41+
root.right.right.right = TreeNode(7)
42+
43+
res = DeepestLeft()
44+
find_deepest_left(root, True, 1, res)
45+
if res.Node:
46+
print(res.Node.val)

‎algorithms/tree/invert_tree.py‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
# invert a binary tree
22

33
def reverse(root):
4-
if not root:
4+
if root is None:
55
return
66
root.left, root.right = root.right, root.left
77
if root.left:

‎algorithms/tree/is_balanced.py‎

Lines changed: 22 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -1,33 +1,36 @@
1-
21
def is_balanced(root):
2+
return __is_balanced_recursive(root)
3+
4+
5+
def __is_balanced_recursive(root):
36
"""
47
O(N) solution
58
"""
6-
return -1 != get_depth(root)
9+
return -1 != __get_depth(root)
10+
711

8-
def get_depth(root):
12+
def __get_depth(root):
913
"""
1014
return 0 if unbalanced else depth + 1
1115
"""
12-
if not root:
16+
if root is None:
1317
return 0
14-
left = get_depth(root.left)
15-
right = get_depth(root.right)
16-
if abs(left-right) > 1 or left == -1 or right == -1:
18+
left = __get_depth(root.left)
19+
right = __get_depth(root.right)
20+
if abs(left-right) > 1 or -1 in [left, right]:
1721
return -1
1822
return 1 + max(left, right)
1923

20-
################################
2124

22-
def is_balanced(root):
23-
"""
24-
O(N^2) solution
25-
"""
26-
left = max_height(root.left)
27-
right = max_height(root.right)
28-
return abs(left-right) <= 1 and is_balanced(root.left) and is_balanced(root.right)
25+
# def is_balanced(root):
26+
# """
27+
# O(N^2) solution
28+
# """
29+
# left = max_height(root.left)
30+
# right = max_height(root.right)
31+
# return abs(left-right) <= 1 and is_balanced(root.left) and is_balanced(root.right)
2932

30-
def max_height(root):
31-
if not root:
32-
return 0
33-
return max(max_height(root.left), max_height(root.right)) + 1
33+
# def max_height(root):
34+
# if root is None:
35+
# return 0
36+
# return max(max_height(root.left), max_height(root.right)) + 1

‎algorithms/tree/is_subtree.py‎

Lines changed: 2 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -64,10 +64,8 @@ def is_subtree(big, small):
6464

6565

6666
def comp(p, q):
67-
if not p and not q:
67+
if p is None and q is None:
6868
return True
69-
if p and q:
69+
if p is not None and q is not None:
7070
return p.val == q.val and comp(p.left,q.left) and comp(p.right, q.right)
7171
return False
72-
73-

‎algorithms/tree/is_symmetric.py‎

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -21,28 +21,28 @@
2121

2222
# TC: O(b) SC: O(log n)
2323
def is_symmetric(root):
24-
if not root:
24+
if root is None:
2525
return True
2626
return helper(root.left, root.right)
2727

2828

2929
def helper(p, q):
30-
if not p and not q:
30+
if p is None and q is None:
3131
return True
32-
if not p or not q or q.val != p.val:
32+
if p is not None or q is not None or q.val != p.val:
3333
return False
3434
return helper(p.left, q.right) and helper(p.right, q.left)
3535

3636

3737
def is_symmetric_iterative(root):
38-
if not root:
38+
if root is None:
3939
return True
4040
stack = [[root.left, root.right]]
4141
while stack:
4242
left, right = stack.pop() # popleft
43-
if not left and not right:
43+
if left is None and right is None:
4444
continue
45-
if not left or not right:
45+
if left is None or right is None:
4646
return False
4747
if left.val == right.val:
4848
stack.append([left.left, right.right])

‎algorithms/tree/longest_consecutive.py‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -30,15 +30,15 @@ def longest_consecutive(root):
3030
:type root: TreeNode
3131
:rtype: int
3232
"""
33-
if not root:
33+
if root is None:
3434
return 0
3535
max_len = 0
3636
dfs(root, 0, root.val, max_len)
3737
return max_len
3838

3939

4040
def dfs(root, cur, target, max_len):
41-
if not root:
41+
if root is None:
4242
return
4343
if root.val == target:
4444
cur += 1

‎algorithms/tree/lowest_common_ancestor.py‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -28,10 +28,10 @@ def lca(root, p, q):
2828
:type q: TreeNode
2929
:rtype: TreeNode
3030
"""
31-
if not root or root is p or root is q:
31+
if root is None or root is p or root is q:
3232
return root
3333
left = lca(root.left, p, q)
3434
right = lca(root.right, p, q)
35-
if left and right:
35+
if left is not None and right is not None:
3636
return root
3737
return left if left else right

0 commit comments

Comments
 (0)