"""
Definition of ListNode
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
@param head: the head of linked list.
@return: a middle node of the linked list
"""
def middleNode(self, head):
# write your code here
if not head:
return None
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
Validate Binary Search Tree – Python 3 (Week 18 – 04)
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: The root of binary tree.
@return: True if the binary tree is BST, or false
"""
def isValidBST(self, root):
# write your code here
if root is None:
return True
stack = []
while root:
stack.append(root)
root = root.left
last_node = stack[-1]
while stack:
node = stack.pop()
if node.right:
node = node.right
while node:
stack.append(node)
node = node.left
if stack:
if stack[-1].val <= last_node.val:
return False
last_node = stack[-1]
return True
Time Space O(n).
Closest Binary Search Tree Value – Python 3 (Week 18 – 03)
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: the given BST
@param target: the given target
@return: the value in the BST that is closest to the target
"""
def closestValue(self, root, target):
if root is None:
return None
lower = self.get_lower_bound(root, target)
upper = self.get_upper_bound(root, target)
if lower is None:
return upper.val
if upper is None:
return lower.val
if target - lower.val < upper.val - target:
return lower.val
return upper.val
def get_lower_bound(self, root, target):
# get the largest node that < target
if root is None:
return None
if target < root.val:
return self.get_lower_bound(root.left, target)
lower = self.get_lower_bound(root.right, target)
return root if lower is None else lower
def get_upper_bound(self, root, target):
# get the smallest node that >= target
if root is None:
return None
if target > root.val:
return self.get_upper_bound(root.right, target)
upper = self.get_upper_bound(root.left, target)
return root if upper is None else upper
Time O(n). Space O(n).
Binary Search Tree Iterator – Python 3 (Week 18 – 02)
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: the given BST
@param k: the given k
@return: the kth smallest element in BST
"""
def kthSmallest(self, root, k):
# write your code here
dummy = TreeNode(0)
dummy.right = root
stack = [dummy]
for i in range(k):
node = stack.pop()
if node.right:
node = node.right
while node:
stack.append(node)
node = node.left
if not stack:
return None
return stack[-1].val
Time O(n+k). Space O(n).
Binary Search Tree Iterator – Python 3 (Week 18 – 01)
Solution 1
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
Example of iterate a tree:
iterator = BSTIterator(root)
while iterator.hasNext():
node = iterator.next()
do something for node
"""
class BSTIterator:
"""
@param: root: The root of binary tree.
"""
def __init__(self, root):
# do intialization if necessary
self.stack = []
while root:
self.stack.append(root)
root = root.left
"""
@return: True if there has next node, or false
"""
def hasNext(self):
# write your code here
return len(self.stack) > 0
"""
@return: return next node
"""
def next(self):
# write your code here
node = self.stack[-1]
if node.right:
n = node.right
while n:
self.stack.append(n)
n = n.left
else:
n = self.stack.pop()
while self.stack and self.stack[-1].right == n:
n = self.stack.pop()
return node
Time, Space O(n).
Solution 2
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
Example of iterate a tree:
iterator = BSTIterator(root)
while iterator.hasNext():
node = iterator.next()
do something for node
"""
class BSTIterator:
"""
@param: root: The root of binary tree.
"""
def __init__(self, root):
# do intialization if necessary
dummy = TreeNode(0)
dummy.right = root
self.stack = [dummy]
self.next()
"""
@return: True if there has next node, or false
"""
def hasNext(self, ):
# write your code here
return len(self.stack) > 0
"""
@return: return next node
"""
def next(self, ):
# write your code here
node = self.stack.pop()
next_node = node
if node.right:
node = node.right
while node:
self.stack.append(node)
node = node.left
return next_node
Expression Add Operators – Python 3 (Week 17 – 20)
import math
class Solution:
"""
@param n: An integer
@return: a list of combination
"""
def getFactors(self, n):
# write your code here
result = []
self.helper(result, [], n, 2);
return result
def helper(self, result, item, n, start):
if n == 1:
if len(item) > 1:
result.append(item[:])
return
import math
for i in range(start, int(math.sqrt(n)) + 1):
if n % i == 0:
item.append(i)
self.helper(result, item, n // i, i)
item.pop()
item.append(n)
self.helper(result, item, 1, n)
item.pop()
Letter Combinations of a Kth Lowest Common Ancestor III – Python 3 (Week 17 – 19)
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
this.val = val
this.left, this.right = None, None
"""
class Solution:
"""
@param: root: The root of the binary tree.
@param: A: A TreeNode
@param: B: A TreeNode
@return: Return the LCA of the two nodes.
"""
def lowestCommonAncestor3(self, root, A, B):
# write your code here
a, b, lca = self.helper(root, A, B)
if a and b:
return lca
else:
return None
def helper(self, root, A, B):
if not root:
return False, False, None
left_a, left_b, left_lca = self.helper(root.left, A, B)
right_a, right_b, right_lca = self.helper(root.right, A, B)
a = left_a or right_a or root == A
b = left_b or right_b or root == B
if root == A or root == B:
return a, b, root
if left_lca is not None and right_lca is not None:
return a, b, root
if left_lca is not None:
return a, b, left_lca
if right_lca is not None:
return a, b, right_lca
return a, b, None
Binary Tree Paths – Python 3 (Week 17 – 18)
Solution 1 Traversal
class Solution:
"""
@param root: the root of the binary tree
@return: all root-to-leaf paths
"""
def binaryTreePaths(self, root):
# write your code here
if root is None:
return []
result = []
self.dfs(root, [str(root.val)], result)
return result
def dfs(self, node, path, result):
if node.left is None and node.right is None:
result.append('->'.join(path))
return
if node.left:
path.append(str(node.left.val))
self.dfs(node.left, path, result)
path.pop()
if node.right:
path.append(str(node.right.val))
self.dfs(node.right, path, result)
path.pop()
Solution 2 Divide Conquer
class Solution:
"""
@param root: the root of the binary tree
@return: all root-to-leaf paths
"""
def binaryTreePaths(self, root):
# write your code here
if root is None:
return []
if root.left is None and root.right is None:
return [str(root.val)]
leftPaths = self.binaryTreePaths(root.left)
rightPaths = self.binaryTreePaths(root.right)
paths = []
for path in leftPaths + rightPaths:
paths.append(str(root.val) + '->' + path)
return paths
Time O(n). Space O(n).
Fast Power – Python 3 (Week 17 – 17)
Solution 1
class Solution:
"""
@param a: A 32bit integer
@param b: A 32bit integer
@param n: A 32bit integer
@return: An integer
"""
def fastPower(self, a, b, n):
# write your code here
ans = 1
while n > 0:
if n % 2 == 1:
ans = (ans * a) % b
a = a * a % b
n = n // 2
return ans % b
Time O(logn). Space O(1).
Solution 2
class Solution:
"""
@param a: A 32bit integer
@param b: A 32bit integer
@param n: A 32bit integer
@return: An integer
"""
def fastPower(self, a, b, n):
# write your code here
if n == 0:
return 1 % b
power = self.fastPower(a, b, n // 2)
power = (power * power) % b
if n % 2 == 1:
power = (power * a) % b
return power
Time O(logn). Space O(logn).
Search in a Big Sorted Array – Python 3 (Week 17 – 16)
Solution 1
class Solution:
"""
@param: reader: An instance of ArrayReader.
@param: target: An integer
@return: An integer which is the first index of target.
"""
def searchBigSortedArray(self, reader, target):
# write your code here
start, end = 0, 1
while reader.get(end) < target:
end = end * 2 + 1
while start + 1 < end:
mid = start + (end - start) // 2
print(mid)
if reader.get(mid) < target:
start = mid
else:
end = mid
if reader.get(start) == target:
return start
if reader.get(end) == target:
return end
return -1
O(logn) time, n is the first index of the given target number.
Solution 2
class Solution:
"""
@param: reader: An instance of ArrayReader.
@param: target: An integer
@return: An integer which is the first index of target.
"""
def searchBigSortedArray(self, reader, target):
# write your code here
first = reader.get(0)
if first == target:
return 0
if first > target:
return -1
index, jump = 0, 1
while jump:
while jump and reader.get(index + jump) >= target:
jump = jump // 2
index += jump
jump *= 2
if reader.get(index + 1) == target:
return index + 1
return -1
步步发财 