Given a binary tree, return the sum of values of its deepest leaves.
 
Example 1:

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15

 
Constraints:

The number of nodes in the tree is between 1 and 10^4.
The value of nodes is between 1 and 100.

Source: leetcode | Difficulty: MEDIUM
Tags: Tree algorithms

Graph traversal

Starter code: # Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        

Solutions:
class Solution:

	def deepestLeavesSum(self, root: TreeNode) -> int:
		q = [root]
		while q:
			(pre, q) = (q, [child for p in q for child in [p.left, p.right] if child])
		return sum((node.val for node in pre))


class Solution:
	node_sum = 0
	most_depth = 0

	def deepestLeavesSum(self, root: TreeNode) -> int:
		depth = 0
		self.generate_deepest_node_map(root, depth)
		return self.node_sum

	def generate_deepest_node_map(self, node, depth):
		if node:
			if node.left:
				self.generate_deepest_node_map(node.left, depth + 1)
			if node.right:
				self.generate_deepest_node_map(node.right, depth + 1)
			if not node.right and (not node.left):
				if self.most_depth == depth:
					self.most_depth = depth
					self.node_sum += node.val
				if self.most_depth < depth:
					self.most_depth = depth
					self.node_sum = node.val


from collections import defaultdict

class Solution:

	def deepestLeavesSum(self, root: TreeNode) -> int:
		treeDict = defaultdict(list)

		def treeLevel(root, level):
			if not root:
				return
			else:
				treeDict[level].append(root.val)
			treeLevel(root.left, level + 1)
			treeLevel(root.right, level + 1)
		treeLevel(root, 0)
		return sum(treeDict[list(treeDict.keys())[-1]])


class Solution:

	def deepestLeavesSum(self, root: TreeNode) -> int:
		nxt = [(0, root)]
		tot = 0
		depth = 0
		while nxt:
			(d, cur) = nxt.pop()
			if d == depth:
				tot += cur.val
			elif d > depth:
				tot = cur.val
				depth = d
			nxt.extend([(d + 1, x) for x in [cur.left, cur.right] if x])
		return tot


class Solution:

	def deepestLeavesSum(self, root: TreeNode) -> int:
		s = {}

		def check(root, depth, s):
			if root == None:
				return 0
			if depth not in s:
				s[depth] = [root.val]
			else:
				s[depth].append(root.val)
			check(root.left, depth + 1, s)
			check(root.right, depth + 1, s)
			return s
		check(root, 0, s)
		m = max(s.keys())
		return sum(s[m])


class Solution:

	def deepestLeavesSum(self, root: TreeNode) -> int:
		if not root:
			return 0
		this_q = [root]
		result = 0
		while this_q:
			next_q = []
			temp = 0
			for node in this_q:
				temp += node.val
				if node.left:
					next_q.append(node.left)
				if node.right:
					next_q.append(node.right)
			this_q = next_q
			result = max(0, temp)
		return result


class Solution:

	def deepestLeavesSum(self, root: TreeNode) -> int:

		def maxDepth(rt):
			root = rt
			if root == None:
				return 0
			stack_list = [(root, 1)]
			maxh = 1
			if root.left == None and root.right == None:
				return maxh
			while len(stack_list) != 0:
				(r, v) = stack_list.pop()
				if r.right == None and r.left == None:
					if v > maxh:
						maxh = v
				if r.left != None:
					stack_list.append((r.left, v + 1))
				if r.right != None:
					stack_list.append((r.right, v + 1))
			return maxh
		htmax = maxDepth(root)
		if htmax == 0:
			return 0
		stack_list = [(root, 1)]
		dmax = 0
		if root.left == None and root.right == None:
			return root.val
		maxh = 1
		while len(stack_list) != 0:
			(r, v) = stack_list.pop()
			if r.right == None and r.left == None:
				if v > maxh:
					maxh = v
			if r.left != None:
				stack_list.append((r.left, v + 1))
				if v + 1 == htmax:
					dmax = dmax + r.left.val
			if r.right != None:
				stack_list.append((r.right, v + 1))
				if v + 1 == htmax:
					dmax = dmax + r.right.val
		return dmax


class Solution:

	def deepestLeavesSum(self, root: TreeNode) -> int:
		s = 0
		q = deque()
		temp = deque()
		if root == None:
			return s
		q.append(root)
		while q:
			node = q.pop()
			s += node.val
			if node.left:
				temp.append(node.left)
			if node.right:
				temp.append(node.right)
			if not q:
				if not temp:
					return s
				else:
					q = temp
					temp = deque()
					s = 0
		return


class Solution:

	def deepestLeavesSum(self, root: TreeNode) -> int:
		if not root:
			return None
		queue = []
		queue.append(root)
		result = []
		while len(queue) > 0:
			levellength = len(queue)
			temp = []
			for i in range(levellength):
				node = queue.pop(0)
				temp.append(node.val)
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
			if len(temp) > 0:
				result.append(temp)
		return sum(result[-1])


import collections

class Solution:

	def deepestLeavesSum(self, root: TreeNode) -> int:
		(total, maxLevel) = (0, 0)

		def helper(node, level):
			if not node:
				return
			nonlocal total
			nonlocal maxLevel
			print((total, maxLevel, node.val, level))
			if level > maxLevel:
				print(('here', level, maxLevel))
				total = node.val
				maxLevel = level
			elif level == maxLevel:
				total += node.val
			helper(node.left, level + 1)
			helper(node.right, level + 1)
		helper(root, 0)
		print(total)
		return total


import queue

class Solution:

	def deepestLeavesSum(self, root: TreeNode) -> int:
		q = queue.deque()
		q.append(root)
		ans = 0
		while q:
			ans = 0
			for _ in range(len(q)):
				cur_node = q.popleft()
				ans += cur_node.val
				if cur_node.left:
					q.append(cur_node.left)
				if cur_node.right:
					q.append(cur_node.right)
		return ans


class Solution:

	def deepestLeavesSum(self, root: TreeNode) -> int:
		stack = [(root, 0)]
		if not root:
			return 0
		leaf_nodes = []
		(max_depth, deepest_sum) = (0, 0)
		while stack:
			(node, depth) = stack.pop()
			if depth > max_depth:
				max_depth = depth
				deepest_sum = node.val
			elif depth == max_depth:
				deepest_sum += node.val
			if node.right:
				stack.append((node.right, depth + 1))
			if node.left:
				stack.append((node.left, depth + 1))
		return deepest_sum


class Solution:

	def deepestLeavesSum(self, root: TreeNode) -> int:

		def traverse(node: TreeNode, layer: int, nums: List[int]):
			if node is None:
				return
			while len(nums) < layer + 1:
				nums.append([])
			nums[layer].append(node.val)
			traverse(node.left, layer + 1, nums)
			traverse(node.right, layer + 1, nums)
		by_layer = []
		traverse(root, 0, by_layer)
		return sum(by_layer[-1])


class Solution:

	def deepestLeavesSum(self, root: TreeNode) -> int:
		if root is None:
			return 0
		queue = deque([(root, 0)])
		res = defaultdict(list)
		while queue:
			(top, l) = queue.popleft()
			res[l].append(top.val)
			if top.left:
				queue.append((top.left, l + 1))
			if top.right:
				queue.append((top.right, l + 1))
		maxidx = max(sorted(res))
		return sum(res[maxidx])


class Solution:

	def deepestLeavesSum(self, root: TreeNode) -> int:
		self.sum_ = 0
		self.h = self.getHeight(root)
		self.helper(root, 1)
		return self.sum_

	def helper(self, node, height):
		if not node:
			return
		self.helper(node.left, height + 1)
		self.helper(node.right, height + 1)
		if height == self.h:
			self.sum_ += node.val

	def getHeight(self, node):
		if not node:
			return 0
		return 1 + max(self.getHeight(node.left), self.getHeight(node.right))


class TreeNode:

	def __init__(self, val=0, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right

class Solution:

	def deepestLeavesSum(self, root: TreeNode) -> int:
		queue = deque([root])
		last_t = 0
		while queue:
			l_sum = 0
			for _ in range(len(queue)):
				node = queue.popleft()
				l_sum += node.val
				if node.left is not None:
					queue.append(node.left)
				if node.right is not None:
					queue.append(node.right)
			(l_sum, last_t) = (0, l_sum)
		return last_t


class Solution:

	def findDepth(self, root: TreeNode) -> int:
		if root == None:
			return 0
		if root.left == None and root.right == None:
			return 1
		return 1 + max(self.findDepth(root.left), self.findDepth(root.right))

	def deepestHelper(self, root: TreeNode, c: int, d: int) -> int:
		total = 0
		if root == None:
			return 0
		if c == d:
			return root.val
		return self.deepestHelper(root.left, c + 1, d) + self.deepestHelper(root.right, c + 1, d)

	def deepestLeavesSum(self, root: TreeNode) -> int:
		d = self.findDepth(root)
		return self.deepestHelper(root, 1, d)


class Solution:

	def deepestLeavesSum(self, root: TreeNode) -> int:
		if not root:
			return 0
		q = [root]
		while True:
			q_new = [x.left for x in q if x.left]
			q_new += [x.right for x in q if x.right]
			if not q_new:
				break
			q = q_new
		return sum([node.val for node in q])


class Solution:

	def deepestLeavesSum(self, root: TreeNode) -> int:
		layer = 0
		total = [0]
		self.dfs(root, total, layer)
		print(total)
		return total[len(total) - 1]

	def dfs(self, node, total, layer):
		if layer > len(total) - 1:
			total.append(0)
		if not node.left and (not node.right):
			total[layer] += node.val
		if node.left:
			self.dfs(node.left, total, layer + 1)
		if node.right:
			self.dfs(node.right, total, layer + 1)


class Solution:

	def deepestLeavesSum(self, root: TreeNode) -> int:
		next_level = deque([root])
		while next_level:
			curr_level = next_level
			next_level = deque()
			for node in curr_level:
				if node.left:
					next_level.append(node.left)
				if node.right:
					next_level.append(node.right)
		return sum([node.val for node in curr_level])


from collections import deque

class Solution:

	def deepestLeavesSum(self, root: TreeNode) -> int:
		deep_sum = 0
		depth = 0
		queue = deque()
		queue.append([root, 0])
		while queue:
			(node, curr_depth) = queue.popleft()
			if not node.left and (not node.right):
				if depth < curr_depth:
					deep_sum = node.val
					depth = curr_depth
				else:
					deep_sum += node.val
			else:
				if node.left:
					queue.append([node.left, curr_depth + 1])
				if node.right:
					queue.append([node.right, curr_depth + 1])
		return deep_sum


from collections import deque

class Solution:

	def bfs_helper(self, root):
		deep_sum = 0
		depth = 0
		queue = deque()
		queue.append([root, 0])
		while queue:
			(node, curr_depth) = queue.popleft()
			if not node.left and (not node.right):
				if depth < curr_depth:
					deep_sum = node.val
					depth = curr_depth
				else:
					deep_sum += node.val
			else:
				if node.left:
					queue.append([node.left, curr_depth + 1])
				if node.right:
					queue.append([node.right, curr_depth + 1])
		return deep_sum

	def dfs_helper(self, root):
		deep_sum = 0
		depth = 0
		stack = list()
		stack.append([root, 0])
		while stack:
			(node, curr_depth) = stack.pop()
			if not node.left and (not node.right):
				if depth < curr_depth:
					deep_sum = node.val
					depth = curr_depth
				elif depth == curr_depth:
					deep_sum += node.val
			else:
				if node.left:
					stack.append([node.left, curr_depth + 1])
				if node.right:
					stack.append([node.right, curr_depth + 1])
		return deep_sum

	def deepestLeavesSum(self, root: TreeNode) -> int:
		return self.dfs_helper(root)


class Solution:

	def deepestLeavesSum(self, root: TreeNode) -> int:
		self.sum = 0
		self.deepest_lvl = 0

		def bfs(root: TreeNode, lvl=0):
			if root is None:
				return
			if root.left is None and root.right is None:
				print(root.val, lvl)
				if lvl > self.deepest_lvl:
					self.sum = root.val
					self.deepest_lvl = lvl
				elif lvl == self.deepest_lvl:
					self.sum += root.val
				return
			bfs(root.left, lvl + 1)
			bfs(root.right, lvl + 1)
		bfs(root)
		return self.sum