Given a binary tree, find the largest value in each level.
Example 1:
Input :
        1
       / \
      2   3 
Output : 1 3
Explanation : 
There are two levels in the tree :
1. {1}, max = 1
2. {2, 3}, max = 3
Example 2:
Input :
        4
       / \
      9   2
     / \   \
    3   5   7 
Output : 4 9 7
Explanation : 
There are three levels in the tree:
1. {4}, max = 4
2. {9, 2}, max = 9
3. {3, 5, 7}, max=7
Your task :
You don't need to read input or print anything. Your task is to complete the function largestValues() which takes the root node of the tree as input and returns a vector containing the largest value in each level. 
 
Expected Time Complexity : O(n) , where n = number of nodes
Expected Auxiliary Space : O(n) , where n = number of nodes
 
Constraints : 
1 ≤ Number of nodes ≤ 10^5

Difficulty: EASY
Tags: Tree algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(n) , where n = number of nodes
Expected Auxiliary Space: O(n) , where n = number of nodes

Starter code:
#User function Template for python3

class Solution:
    def largestValues(self, root):
        #code here

Solutions:
class Solution:

	def largestValues(self, root):
		if not root:
			return []
		ans = []
		current = [root]
		while current:
			new_curr = []
			maxx = -999999999
			for node in current:
				maxx = max(maxx, node.data)
				if node.left:
					new_curr.append(node.left)
				if node.right:
					new_curr.append(node.right)
			ans.append(maxx)
			current = new_curr
		return ans


class Solution:

	def largestValues(self, root):
		if not root:
			return []
		ans = []
		current = [root]
		while current:
			new_curr = []
			values = []
			for node in current:
				values.append(node.data)
				if node.left:
					new_curr.append(node.left)
				if node.right:
					new_curr.append(node.right)
			ans.append(values)
			current = new_curr
		max_nums = []
		for lists in ans:
			max_nums.append(max(lists))
		return max_nums


from collections import deque

class Solution:

	def largestValues(self, root):
		queue = deque()
		queue.append(root)
		maximum_ans = []
		while queue:
			size = len(queue)
			maxi = -999
			for _ in range(size):
				node = queue.popleft()
				maxi = max(maxi, node.data)
				if node.left and node.right:
					queue.append(node.left)
					queue.append(node.right)
				elif node.right:
					queue.append(node.right)
				elif node.left:
					queue.append(node.left)
			maximum_ans.append(maxi)
		return maximum_ans


from collections import deque

class Solution:

	def largestValues(self, root):
		if root is None:
			return 0
		q = deque([root])
		p = []
		while q:
			l = []
			n1 = len(q)
			for i in range(n1):
				n = q.popleft()
				l.append(n.data)
				if n.left:
					q.append(n.left)
				if n.right:
					q.append(n.right)
			p.append(max(l))
		return p


from collections import deque

class Solution:

	def largestValues(self, root):
		ans = []
		q = deque([root, None])
		maxval = 0
		while len(q) != 1:
			ele = q.popleft()
			if ele:
				maxval = max(maxval, ele.data)
				if ele.left:
					q.append(ele.left)
				if ele.right:
					q.append(ele.right)
			else:
				ans.append(maxval)
				maxval = 0
				q.append(None)
		ans.append(maxval)
		return ans


class Solution:

	def largestValues(self, root):
		dict = {}
		self.solver(root, dict)
		res = [val for val in dict.values()]
		return res

	def solver(self, root, dict, depth=0):
		if root:
			self.solver(root.left, dict, depth + 1)
			if depth in dict:
				if dict[depth] < root.data:
					dict[depth] = root.data
			else:
				dict[depth] = root.data
			self.solver(root.right, dict, depth + 1)


class Solution:

	def largestValues(self, root):
		queue = [root]
		res = [root.data]
		while queue:
			temp = []
			temp_max = -99999
			for n in queue:
				l = -99999
				r = -99999
				if n.left:
					l = n.left.data
					temp.append(n.left)
				if n.right:
					r = n.right.data
					temp.append(n.right)
				temp_max = max(temp_max, l, r)
			queue = temp
			res.append(temp_max)
		return res[:len(res) - 1]


from collections import deque

class Solution:

	def largestValues(self, root):
		if root is None:
			return
		q = deque()
		result = []
		q.append(root)
		while q:
			max = q[0].data
			size = len(q)
			for i in range(size):
				node = q.popleft()
				if max < node.data:
					max = node.data
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			result.append(max)
		return result


import collections

class Solution:

	def largestValues(self, root):
		if not root:
			return []
		(queue, max_val) = (collections.deque([root]), [])
		while queue:
			level = []
			for i in range(len(queue)):
				node = queue.popleft()
				level.append(node.data)
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
			max_val.append(max(level))
		return max_val


class Solution:

	def helper(self, res, root, d):
		if root == None:
			return
		if d == len(res):
			res.append(root.data)
		else:
			res[d] = max(res[d], root.data)
		self.helper(res, root.left, d + 1)
		self.helper(res, root.right, d + 1)

	def largestValues(self, root):
		global res
		res = []
		self.helper(res, root, 0)
		return res


class Solution:

	def largestValues(self, root):
		value = {}

		def res(rt, val, level=0):
			if rt:
				res(rt.left, val, level + 1)
				if level in val:
					if val[level] < rt.data:
						val[level] = rt.data
				else:
					val[level] = rt.data
				res(rt.right, val, level + 1)
		res(root, value)
		return value.values()


from collections import deque

class Solution:

	def largestValues(self, root):
		if not root:
			return []
		result = []
		queue = deque([root])
		while queue:
			level_size = len(queue)
			max_val = float('-inf')
			for _ in range(level_size):
				node = queue.popleft()
				max_val = max(max_val, node.data)
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
			result.append(max_val)
		return result


class Solution:

	def fun(self, root, digit, ans):
		if root == None:
			return
		if digit >= len(ans):
			ans.append([])
		ans[digit].append(root.data)
		self.fun(root.left, digit + 1, ans)
		self.fun(root.right, digit + 1, ans)

	def largestValues(self, root):
		ans = []
		self.fun(root, 0, ans)
		l = []
		for i in ans:
			if len(i) != 0:
				l.append(max(i))
		return l


def preorder(root, d, level):
	if root is None:
		return
	d.setdefault(level, []).append(root.data)
	preorder(root.left, d, level + 1)
	preorder(root.right, d, level + 1)

class Solution:

	def largestValues(self, root):
		d = dict()
		level = 1
		ans = []
		preorder(root, d, level)
		for k in d:
			ans.append(max(d[k]))
		return ans


class Solution:

	def largestValues(self, root):
		arr = []
		self._largestvalues(root, arr, 0)
		return arr

	def _largestvalues(self, node, arr, num):
		if node is not None:
			if len(arr) <= num:
				arr.append(node.data)
			elif arr[num] < node.data:
				arr[num] = node.data
			self._largestvalues(node.left, arr, num + 1)
			self._largestvalues(node.right, arr, num + 1)


from collections import deque

class Solution:

	def largestValues(self, root):
		q = deque([root])
		ans = []
		while q:
			n = len(q)
			level = []
			for i in range(n):
				t = q.popleft()
				level.append(t.data)
				if t.left:
					q.append(t.left)
				if t.right:
					q.append(t.right)
			ans.append(max(level))
		return ans


import numpy as np

class Solution:

	def largestValues(self, root):
		master = []
		self.root = root

		def level(root, value):
			self.root = root
			if root is None:
				return 0
			if len(master) <= value:
				master.append(self.root.data)
			if self.root.data > master[value]:
				master[value] = self.root.data
			newval = value + 1
			level(root.left, newval)
			level(root.right, newval)
		level(root, 0)
		return master


class Solution:

	def largestValues(self, root):
		res = []
		queue = [root]
		while queue:
			level = []
			vals = []
			for i in queue:
				if i == None:
					continue
				vals.append(i.data)
				level.append(i.left)
				level.append(i.right)
			queue = level
			if len(vals) > 0:
				res.append(max(vals))
		return res


class Solution:

	def largestValues(self, root):
		dir = {}

		def max_level(root, level, dir):
			if not root:
				return
			if not dir.get(level):
				dir[level] = root.data
			else:
				dir[level] = max(dir.get(level), root.data)
			max_level(root.left, level + 1, dir)
			max_level(root.right, level + 1, dir)
		max_level(root, 0, dir)
		list = []
		for i in dir:
			list.append(dir.get(i))
		return list


class Solution:

	def largestValues(self, root):
		ans = []
		dfs(root, 0, ans)
		return ans

def dfs(n, l, ans):
	if not n:
		return
	if len(ans) == l:
		ans.append(n.data)
	ans[l] = max(ans[l], n.data)
	dfs(n.left, l + 1, ans)
	dfs(n.right, l + 1, ans)


from collections import deque

class Solution:

	def largestValues(self, root):
		v = []
		self.helper(root, v, 0)
		return v

	def helper(self, root, v, count):
		if root == None:
			return
		if count == len(v):
			v.append(root.data)
		else:
			v[count] = max(v[count], root.data)
		self.helper(root.left, v, count + 1)
		self.helper(root.right, v, count + 1)


from collections import deque

class Solution:

	def largestValues(self, root):
		if root == None:
			return
		q = deque()
		q.append(root)
		c = []
		while len(q) > 0:
			t = []
			n = len(q)
			for i in range(n):
				temp = q.popleft()
				t.append(temp.data)
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
			c.append(max(t))
		return c


class Solution:

	def largestValues(self, root):
		self.dic = {}

		def traverse(root, level):
			if not root:
				return
			if level in self.dic:
				if root.data > self.dic[level]:
					self.dic[level] = root.data
			else:
				self.dic[level] = root.data
			traverse(root.left, level + 1)
			traverse(root.right, level + 1)
		traverse(root, 0)
		ans = []
		for i in range(len(self.dic)):
			ans.append(self.dic[i])
		return ans


class Solution:

	def height(self, root):
		if root is None:
			return 0
		return 1 + max(self.height(root.left), self.height(root.right))

	def largestValues(self, root):
		res = []
		temp = []
		temp1 = []
		if root is not None:
			temp.append(root)
		level = self.height(root)
		y = 1
		while y <= level:
			max = 0
			if y % 2 == 0:
				while len(temp1) > 0:
					val = temp1.pop()
					if val.left is not None:
						temp.append(val.left)
					if val.right is not None:
						temp.append(val.right)
					if val.data > max:
						max = val.data
			else:
				while len(temp) > 0:
					val = temp.pop()
					if val.left is not None:
						temp1.append(val.left)
					if val.right is not None:
						temp1.append(val.right)
					if val.data > max:
						max = val.data
			res.append(max)
			y += 1
		return res


class Solution:

	def largestValues(self, root):
		q = deque()
		q.append(root)
		arr = []
		while q:
			l = len(q)
			x = -999
			for i in range(l):
				temp = q.popleft()
				y = temp.data
				x = max(x, y)
				if temp.left:
					q.extend([temp.left])
				if temp.right:
					q.extend([temp.right])
			arr.extend([x])
		return arr


class Solution:

	def largestValues(self, root):
		if root is None:
			return -1
		st = []
		st.append(root)
		ans = []
		while len(st) > 0:
			test = []
			max = -1
			while len(st) > 0:
				x = st.pop()
				if x.data > max:
					max = x.data
				if x.right is not None:
					test.append(x.right)
				if x.left is not None:
					test.append(x.left)
			ans.append(max)
			max = -1
			st = test
		return ans


from collections import deque

class Solution:

	def largestValues(self, root):
		s1 = []
		queue = deque()
		queue.append(root)
		while queue:
			maxi = -999
			for i in range(len(queue)):
				curr = queue.popleft()
				maxi = max(maxi, curr.data)
				if curr.left:
					queue.extend([curr.left])
				if curr.right:
					queue.extend([curr.right])
			s1.append(maxi)
		return s1


class Solution:
	max1 = 0
	l = []

	def traverse(self, root, count):
		if root == None:
			return
		while count > len(self.l):
			self.l.append(0)
		self.traverse(root.left, count + 1)
		self.l[count - 1] = max(self.l[count - 1], root.data)
		self.traverse(root.right, count + 1)

	def largestValues(self, root):
		self.l = []
		self.traverse(root, 1)
		return self.l


class Solution:

	def largestValues(self, root):
		A = []
		self.x(root, A, 0)
		D = {}
		for i in A:
			if i[1] not in D.keys():
				D[i[1]] = i[0]
			elif i[0] > D[i[1]]:
				D[i[1]] = i[0]
		C = []
		for j in sorted(D.keys()):
			C.append(D[j])
		return C

	def x(self, root, A, hd):
		if root is None:
			return
		self.x(root.left, A, hd + 1)
		A.append([root.data, hd])
		self.x(root.right, A, hd + 1)


class Solution:

	def largestValues(self, root):
		q = deque([root])
		ans = []
		while q:
			l = []
			s = len(q)
			for i in range(s):
				t = q.popleft()
				l.append(t.data)
				if t.left:
					q.append(t.left)
				if t.right:
					q.append(t.right)
			ans.append(max(l))
		return ans


from collections import deque

class Solution:

	def largestValues(self, root):
		res = []
		if not root:
			return res
		queue = deque()
		queue.append(root)
		while queue:
			sz = len(queue)
			mx = -1
			for i in range(sz):
				temp = queue.popleft()
				mx = max(mx, temp.data)
				if temp.left:
					queue.append(temp.left)
				if temp.right:
					queue.append(temp.right)
			res.append(mx)
		return res


class Solution:

	def largestValues(self, root):
		map = {}
		ans = []
		self.Util(root, 0, map)
		for i in range(min(map.keys()), max(map.keys()) + 1):
			ans.append(map[i])
		return ans

	def Util(self, root, level, map):
		if not root:
			return None
		import sys
		if map.get(level, -sys.maxsize) == -sys.maxsize:
			map[level] = root.data
		elif root.data > map[level]:
			map[level] = root.data
		self.Util(root.left, level + 1, map)
		self.Util(root.right, level + 1, map)


class Solution:

	def __init__(self):
		self.dp = dict()
		self.h = 0

	def run(self, root, h=0):
		if root == None:
			return None
		self.h = max(h, self.h)
		if self.dp.get(h) == None:
			self.dp[h] = root.data
		else:
			self.dp[h] = max(self.dp[h], root.data)
		self.run(root.left, h + 1)
		self.run(root.right, h + 1)

	def largestValues(self, root):
		self.run(root)
		return [self.dp[x] for x in range(self.h + 1)]


class Solution:

	def largestValues(self, root):

		def findLevel(d1, r1, level):
			if not r1:
				return level
			if level not in d1:
				d1[level] = r1.data
			else:
				d1[level] = max(d1[level], r1.data)
			return max(findLevel(d1, r1.left, level + 1), findLevel(d1, r1.right, level + 1))
		ans = []
		if not root:
			return
		d1 = {}
		lvl = 0
		max_level = findLevel(d1, root, lvl)
		for i in range(max_level):
			ans.append(d1[i])
		return ans


class Solution:

	def largestValues(self, root):
		global l, a
		a = [[]]
		l = 0

		def sol(root, level):
			global l, a
			if root:
				if l < level:
					l = level
					a.append([])
				a[level].append(root.data)
				sol(root.left, level + 1)
				sol(root.right, level + 1)
		sol(root, 0)
		m = []
		for i in a:
			m.append(max(i))
		return m


class Solution:

	def largestValues(self, root):
		arr = []
		self.levelMax(root, arr, 0)
		return arr

	def levelMax(self, root, arr, level):
		if not root:
			return
		if len(arr) == level:
			arr.append(root.data)
		arr[level] = max(arr[level], root.data)
		level += 1
		self.levelMax(root.left, arr, level)
		self.levelMax(root.right, arr, level)
		return


class Solution:

	def largestValues(self, root):
		(l, l1) = ([], [])

		def levelorder(root, level, l):
			if root is None:
				return
			if len(l) <= level:
				l.append([])
			l[level].append(root.data)
			levelorder(root.left, level + 1, l)
			levelorder(root.right, level + 1, l)
		levelorder(root, 0, l)
		for i in l:
			l1.append(max(i))
		return l1


class Solution:

	def in_order(self, root, lvl, nv, mlvl):
		if root is None:
			return
		self.in_order(root.left, lvl + 1, nv, mlvl)
		self.in_order(root.right, lvl + 1, nv, mlvl)
		mlvl[0] = max(lvl, mlvl[0])
		if lvl not in nv:
			nv[lvl] = [root.data]
		else:
			nv[lvl].append(root.data)

	def largestValues(self, root):
		nv = {}
		mlvl = [0]
		self.in_order(root, 0, nv, mlvl)
		ans = [0] * (mlvl[0] + 1)
		for (k, v) in nv.items():
			ans[k] = max(v)
		return ans


class Solution:

	def largestValues(self, root):
		q = deque([root])
		ans = []
		while q:
			n = len(q)
			level = []
			for i in range(n):
				curr = q.popleft()
				level.append(curr.data)
				if curr.left:
					q.append(curr.left)
				if curr.right:
					q.append(curr.right)
			ans.append(max(level))
		return ans


class Solution:

	def largestValues(self, root):

		def largest_in_level(root):
			nonlocal level, largest
			if root is None:
				return
			if len(largest) < level + 1:
				largest.append(root.data)
			elif largest[level] < root.data:
				largest[level] = root.data
			level += 1
			largest_in_level(root.left)
			largest_in_level(root.right)
			level -= 1
			return
		level = 0
		largest = []
		largest_in_level(root)
		return largest


class Solution:

	def __init__(self):
		self.level = {}

	def pre(self, root, l):
		if l in self.level:
			self.level[l].append(root.data)
		else:
			self.level[l] = [root.data]
		if root.left != None:
			self.pre(root.left, l + 1)
		if root.right != None:
			self.pre(root.right, l + 1)

	def largestValues(self, root):
		self.pre(root, 0)
		res = []
		for i in self.level.keys():
			res.append(max(self.level[i]))
		return res


class Solution:

	def largestValues(self, root):
		d = {}
		level = 0
		self.helper(root, level, d)
		l = []
		for i in d:
			l.append(max(d[i]))
		del d
		return l

	def helper(self, root, level, d):
		if not root:
			return
		if level not in d:
			d[level] = [root.data]
		else:
			d[level].append(root.data)
		self.helper(root.left, level + 1, d)
		self.helper(root.right, level + 1, d)


INT_MIN = -(1 << 63)

class Solution:

	def helper(self, root, res, level):
		if root is None:
			return 0
		if level == len(res):
			res.append(root.data)
		else:
			res[level] = max(res[level], root.data)
		self.helper(root.left, res, level + 1)
		self.helper(root.right, res, level + 1)

	def largestValues(self, root):
		if root is None:
			return []
		res = []
		self.helper(root, res, 0)
		return res


from collections import deque

class Solution:

	def largestValues(self, root):
		res = []
		queue = deque()
		queue.append(root)
		elements = 1
		newelements = 0
		boolean = False
		while len(queue) > 0:
			root = queue.popleft()
			if not boolean:
				res.append(root.data)
				boolean = True
			else:
				res.append(max(root.data, res.pop()))
			elements -= 1
			if root.left != None:
				queue.append(root.left)
				newelements += 1
			if root.right != None:
				queue.append(root.right)
				newelements += 1
			if elements == 0:
				elements += newelements
				newelements = 0
				boolean = False
		return res


class Solution:

	def largestValues(self, root):
		level_list = [root]
		level_list_next = []
		max_levels = []
		while level_list:
			max = -1
			for node in level_list:
				if node.data > max:
					max = node.data
				if node.left:
					level_list_next.append(node.left)
				if node.right:
					level_list_next.append(node.right)
			level_list = level_list_next
			level_list_next = []
			max_levels.append(max)
		return max_levels


import sys

class Solution:

	def largestValues(self, root):
		if root == None:
			return []
		q = deque()
		q.append(root)
		res = []
		while len(q):
			sz = len(q)
			mx = 0
			for i in range(sz):
				ele = q.popleft()
				if ele.left:
					q.append(ele.left)
				if ele.right:
					q.append(ele.right)
				mx = max(mx, ele.data)
			res.append(mx)
		return res


def large(root, level, d):
	if root is None:
		return
	if level in d:
		if root.data > d[level]:
			d[level] = root.data
	if level not in d:
		d[level] = root.data
	large(root.left, level + 1, d)
	large(root.right, level + 1, d)

class Solution:

	def largestValues(self, root):
		d = {}
		array = []
		large(root, 1, d)
		for i in range(1, len(d) + 1):
			array.append(d[i])
		return array


class Solution:

	def largestValues(self, root):
		lst = []
		if root == None:
			return
		queue = deque()
		queue.append(root)
		while queue:
			n = len(queue)
			maxValue = -1000000000.0
			while n:
				node = queue.popleft()
				maxValue = max(maxValue, node.data)
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
				n = n - 1
			lst.append(maxValue)
		return lst


import queue

class Solution:

	def largestValues(self, root):

		def helper(x):
			ans = []
			q = deque()
			t = -99
			if not x:
				return ans
			q.append(x)
			while q:
				l = len(q)
				for i in range(l):
					a = q.popleft()
					if a.left:
						q.append(a.left)
					if a.right:
						q.append(a.right)
					t = max(t, a.data)
				ans.append(t)
				t = -99
			return ans
		a = helper(root)
		return a


class Solution:

	def largestValues(self, root):
		d = []

		def findmax(root, h):
			if root == None:
				return
			if h + 1 > len(d):
				d.append(root.data)
			elif root.data > d[h]:
				d[h] = root.data
			findmax(root.left, h + 1)
			findmax(root.right, h + 1)
		findmax(root, 0)
		return d


class Solution:

	def largestValues(self, root):
		children = [root]
		maxs = []
		while True:
			if not len(children):
				break
			maxs.append(max(list(map(lambda x: x.data, children))))
			grandkids = []
			for child in children:
				grandkids.append(child.left)
				grandkids.append(child.right)
			children = list(filter(lambda x: x != None, grandkids))
		return maxs


class Solution:

	def largestValues(self, root):
		if not root:
			return None

		def helper(node, h):
			if not node:
				return
			if h not in values:
				values[h] = node.data
			else:
				values[h] = max(values[h], node.data)
			helper(node.left, h + 1)
			helper(node.right, h + 1)
		values = {}
		helper(root, 0)
		ans = []
		for (key, item) in values.items():
			ans.append(item)
		return ans


class Solution:

	def largestValues(self, root):
		if not root:
			return
		level = 1
		dict1 = {}

		def solve(root, level, dict1):
			if not root:
				return
			if level not in dict1:
				dict1[level] = root.data
			else:
				dict1[level] = max(dict1[level], root.data)
			solve(root.left, level + 1, dict1)
			solve(root.right, level + 1, dict1)
		solve(root, level, dict1)
		ans = []
		for (i, j) in sorted(dict1.items()):
			ans.append(j)
		return ans


class Solution:

	def largestValues(self, root):
		result = []
		q = [root]
		while q:
			tsum = -float('inf')
			temp = []
			for i in q:
				tsum = max(tsum, i.data)
				if i.left:
					temp.append(i.left)
				if i.right:
					temp.append(i.right)
			result.append(tsum)
			q = temp
		return result


import collections

class Solution:

	def largestValues(self, root):
		q = collections.deque()
		q.append(root)
		Max = []
		while q:
			qLen = len(q)
			temp_max = float('-inf')
			for i in range(qLen):
				cur = q.popleft()
				if temp_max < cur.data:
					temp_max = cur.data
				if cur.left:
					q.append(cur.left)
				if cur.right:
					q.append(cur.right)
			Max.append(temp_max)
		return Max


from collections import deque
from math import inf

class Solution:

	def largestValues(self, root):
		q = deque()
		q.append(root)
		lst = []
		while q:
			maxi = -inf
			for i in range(len(q)):
				temp = q.popleft()
				maxi = max(maxi, temp.data)
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
			lst.append(maxi)
		return lst


import collections
from collections import deque

class Solution:

	def largestValues(self, root):
		res = []
		a = []
		q = collections.deque()
		q.append(root)
		while q:
			ql = len(q)
			l = []
			for i in range(ql):
				x = q.popleft()
				if x:
					l.append(x.data)
					q.append(x.left)
					q.append(x.right)
			if l:
				res.append(l)
		for i in res:
			z = max(i)
			a.append(z)
		return a


class Solution:

	def largestValues(self, root):

		def height(root):
			if not root:
				return 0
			else:
				lheight = height(root.left)
				rheight = height(root.right)
				return max(lheight, rheight) + 1

		def getcurrentmax(root, level, arr):
			if not root:
				return
			if level == 1:
				if root.data > arr[0]:
					arr[0] = root.data
			if level > 1:
				getcurrentmax(root.left, level - 1, arr)
				getcurrentmax(root.right, level - 1, arr)
			return arr
		res = []
		h = height(root)
		for i in range(1, h + 1):
			res.append(getcurrentmax(root, i, [-1])[0])
		return res


class Solution:

	def largestValues(self, root):
		res = []
		queue = []
		queue.append(root)
		while queue:
			max = 0
			for i in queue:
				if i.data > max:
					max = i.data
			temp = []
			for i in queue:
				if i.left:
					temp.append(i.left)
				if i.right:
					temp.append(i.right)
			queue = temp
			res.append(max)
		return res


class Solution:

	def largestValues(self, root):
		self.ans = []
		self.solve(root, 0)
		return self.ans

	def solve(self, root, l):
		if root == None:
			return
		if l < len(self.ans):
			if self.ans[l] < root.data:
				self.ans[l] = root.data
		else:
			self.ans.append(root.data)
		self.solve(root.left, l + 1)
		self.solve(root.right, l + 1)


class Solution:

	def transversal(self, root, list1, level):
		if root is None:
			return
		if level < len(list1):
			if root.data > list1[level]:
				list1[level] = root.data
		else:
			list1.append(root.data)
		self.transversal(root.left, list1, level + 1)
		self.transversal(root.right, list1, level + 1)

	def largestValues(self, root):
		res = []
		self.transversal(root, res, 0)
		return res


class Solution:

	def largestValues(self, root):
		cur = [root]
		nex = []
		res = []
		while cur:
			temp = []
			for i in cur:
				temp.append(i.data)
				if i.left:
					nex.append(i.left)
				if i.right:
					nex.append(i.right)
			res.append(max(temp))
			cur = nex
			nex = []
		return res


class Solution:

	def largestValues(self, root):
		ans = []
		queue = [root]
		level = []
		while queue != [] and root is not None:
			l = []
			for node in queue:
				l.append(node.data)
				if node.left:
					level.append(node.left)
				if node.right:
					level.append(node.right)
			ans.append(max(l))
			queue = level
			level = []
		return ans


class Solution:

	def largestValues(self, root):
		if not root:
			return
		ans = []
		q = []
		q.append(root)
		while len(q) > 0:
			b = []
			li = []
			while len(q) > 0:
				node = q.pop(0)
				li.append(node.data)
				if node.left:
					b.append(node.left)
				if node.right:
					b.append(node.right)
			ans.append(max(li))
			q = b
		return ans


class Solution:

	def largestValues(self, root):
		final = []
		current_level = [root]
		next_level = []
		tmp = 0
		while current_level:
			node = current_level.pop(0)
			tmp = max(tmp, node.data)
			if node.left:
				next_level.append(node.left)
			if node.right:
				next_level.append(node.right)
			if not current_level:
				(current_level, next_level) = (next_level, current_level)
				final.append(tmp)
				tmp = 0
		return final


class Solution:

	def Preorder(self, res, root, d):
		if not root:
			return
		if d == len(res):
			res.append(root.data)
		else:
			res[d] = max(res[d], root.data)
		self.Preorder(res, root.left, d + 1)
		self.Preorder(res, root.right, d + 1)
		return res

	def largestValues(self, root):
		res = []
		result = Solution().Preorder(res, root, 0)
		return result


class Solution:

	def largestValues(self, root):

		def large(res, root, d):
			if root is None:
				return
			if len(res) == d:
				res.append(root.data)
			else:
				res[d] = max(res[d], root.data)
			large(res, root.left, d + 1)
			large(res, root.right, d + 1)
		res = []
		large(res, root, 0)
		return res


class Solution:

	def get(self, root, arr, lev):
		if not root:
			return
		arr.append([root.data, lev])
		self.get(root.right, arr, lev + 1)
		self.get(root.left, arr, lev + 1)

	def largestValues(self, root):
		arr = []
		arr.append([root.data, 0])
		self.get(root.right, arr, 1)
		self.get(root.left, arr, 1)
		dep = arr[len(arr) - 1][1] + 1
		ar = [0] * dep
		for a in arr:
			l = a[1]
			if ar[l] < a[0]:
				ar[l] = a[0]
		return ar


class Solution:

	def largestValues(self, root):

		def func(root, arr, ind):
			if not root:
				return
			if ind == len(arr):
				arr.append(root.data)
			else:
				arr[ind] = max(arr[ind], root.data)
			func(root.left, arr, ind + 1)
			func(root.right, arr, ind + 1)
			return arr
		return func(root, [], 0)


class Solution:

	def largestValues(self, root):
		res = []
		self.helper(res, root, 0)
		return res

	def helper(self, res, root, depth):
		if not root:
			return
		if depth == len(res):
			res.append(root.data)
		else:
			res[depth] = max(res[depth], root.data)
		self.helper(res, root.left, depth + 1)
		self.helper(res, root.right, depth + 1)


from collections import deque

class Solution:

	def largestValues(self, root):
		if root is None:
			return []
		l = deque([root])
		l2 = []
		while len(l) > 0:
			l1 = []
			y = len(l)
			for i in range(y):
				x = l.popleft()
				if x.left:
					l.append(x.left)
				if x.right:
					l.append(x.right)
				l1.append(x.data)
			l2.append(max(l1))
		return l2


class Solution:

	def largestValues(self, root):
		map = {}

		def help(root, l):
			nonlocal map
			if root == None:
				return
			if l not in map:
				map[l] = root.data
			elif map[l] < root.data:
				map[l] = root.data
			help(root.left, l + 1)
			help(root.right, l + 1)
		help(root, 0)
		ans = []
		for i in map:
			ans.append(map[i])
		return ans


class Solution:

	def largestValues(self, root):
		if root == None:
			return None
		q = deque()
		q.append(root)
		res = []
		while len(q) > 0:
			count = len(q)
			ans = []
			for i in range(count):
				temp = q.popleft()
				ans.append(temp.data)
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
			res.append(max(ans))
		return res


class Solution:

	def largestValues(self, root):
		ans = []
		if not root:
			return ans
		queue = [root]
		while queue:
			newLevel = []
			maxx = float('-inf')
			for child in queue:
				maxx = max(maxx, child.data)
				if child.right:
					newLevel.append(child.right)
				if child.left:
					newLevel.append(child.left)
			ans.append(maxx)
			queue = newLevel
		return ans


class Solution:

	def largestValues(self, root):

		def getLargestValues(root, level, result):
			if root is None:
				return
			if root.data > result[level]:
				result[level] = root.data
			if level == len(result) - 1:
				result.append(-1)
			getLargestValues(root.left, level + 1, result)
			getLargestValues(root.right, level + 1, result)
		result = [-1]
		getLargestValues(root, 0, result)
		return result[:-1]