Solution to Problem on Slide 3:
A height-balanced binary tree is a tree in which each node's 2 subtrees have heights that do not differ by more than 1. We can get the balance and height of a tree by calling one function get_balance_and_height. Then if that node has a left or right subtree store those subtree's heights and balance by calling the recursive function again. Then store the current height of this node by finding the max of the subtrees. Then perform a height check to see if each subtree satisfies the condition. Then you can call this function on the root node to get the balance of the tree.
def get_balance_and_height(self,node):
h = 0
balanced = True
if node:
hr, hl = 0,0
if node.left:
bl, hl = self.get_balance_and_height(node.left)
balanced = balanced and bl
h = max(h, hl)
if node.right:
br, hr = self.get_balance_and_height(node.right)
balanced = balanced and br
h = max(h, hr)
h+=1
balanced = balanced and (abs(hr-hl)<2)
return balanced, h
def isBalanced(self, root):
return self.get_balance_and_height(root)[0]
Solution from problem on slide 4
For each column, row, and 3x3 square, maintain a set that stores numbers present in those regions. Then iterate through the 9x9 square and add existing elements to those sets. If an item already exists in a set, then that means you have a duplicate so the board is invalid.
row_contains = [set() for i in range(9)]
column_contains = [set() for i in range(9)]
sub_region_contains = [[set() for i in range(3)] for j in range(3)]
for i in range(9):
for j in range(9):
# print(i,j)
ii = i//3
jj = j//3
if board[i][j]!='.':
if board[i][j] in row_contains[i]:
return False
if board[i][j] in column_contains[j]:
return False
if board[i][j] in sub_region_contains[ii][jj]:
return False
row_contains[i].add(board[i][j])
column_contains[j].add(board[i][j])
sub_region_contains[ii][jj].add(board[i][j])
return TrueSolution to Homework ACSL Practice Problem ( Henry's Solution )