Solution to LeetCode 637 Average of Levels in Binary Tree, LeetCode 429 N-ary Tree Level Order Traversal, and LeetCode 515 Find Largest Value in Each Tree Row.
LeetCode 637
Average of Levels in Binary Tree. (Easy) [link]
Level-order traversal (LC102). Time complexity O(n).
# 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 averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
results = []
if not root: return results
que = deque([root])
while que:
res = []
size = len(que)
for i in range(size):
cur = que.popleft()
res.append(cur.val)
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
results.append(sum(res)/len(res))
return results
LeetCode 429
N-ary Tree Level Order Traversal (Medium) [link]
Time complexity O(n).
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
results = []
if not root: return results
que = deque([root])
while que:
size = len(que)
res = []
for i in range(size):
cur = que.popleft()
res.append(cur.val)
if cur.children:
que.extend(cur.children)
results.append(res)
return results
LeetCode 515
Find Largest Value in Each Tree Row (Medium) [link]
Level-order traversal (LC 102). Time complexity O(n).
# 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 largestValues(self, root: Optional[TreeNode]) -> List[int]:
results = []
if not root: return results
que = deque([root])
while que:
size = len(que)
res = []
for i in range(size):
cur = que.popleft()
res.append(cur.val)
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
results.append(max(res))
return results
