Tree: Finding Largest Value in each row of binary tree BFS Python
Wed Aug 03 2022 20:16:32 GMT+0000 (Coordinated Universal Time)
Saved by
@bryantirawan
#python
#methods
#queue
#codesignal
#breath
#first
#search
#max
#
# Binary trees are already defined with this interface:
# class Tree(object):
# def __init__(self, x):
# self.value = x
# self.left = None
# self.right = None
import math
def solution(t):
if t is None: return []
stack = [t]
result = []
while len(stack) > 0:
result.append(max(tree.value for tree in stack))
next_row = [tree.left for tree in stack if tree.left] + [tree.right for tree in stack if tree.right]
stack = next_row
return result
#1. Add max value of ‘stack’ to result. 2. Create a new list of all next values for each value in stack. 3. redefine stack to this newly made list. 4. repeat
#alternate solution
def solution(t):
largestValues = []
q = []
height = 0
if t:
q.append([t, height])
while q:
item = q.pop()
node = item[0]
currentHeight = item[1]
if node.left:
q.insert(0, [node.left, currentHeight + 1] )
if node.right:
q.insert(0, [node.right, currentHeight + 1])
checkLargest(node.value, currentHeight, largestValues)
return largestValues
def checkLargest(value, height, largestValues):
if height == len(largestValues):
largestValues.append(value)
else:
if largestValues[height] < value:
largestValues[height] = value
content_copyCOPY
codesignal
Comments