Leetcode: Binary tree level order traversal
Given the root node of a binary tree, print all values in order, meaning from left to right on the same level.
To solve this, we can use the standard breadth-first-search (BFS) algorithm in an iterative fashion with a queue. As an output we use a list and leverage the position -1 to add the current level to the list. For every level we append one new element to the end of the list.
from typing import List, Optional
# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if root is None:
return []
res = []
queue = [[root]]
while len(queue) > 0:
itms = queue[0]
res.append([])
queue.append([])
for item in itms:
res[-1].append(item.val)
if item.left is not None:
queue[-1].append(item.left)
if item.right is not None:
queue[-1].append(item.right)
if len(queue[-1]) == 0:
queue.pop()
queue = queue[1:]
return res
if __name__ == '__main__':
s = Solution().levelOrder
print(s(TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))), [[3], [9,20], [15,7]])
print(s(TreeNode(1)), [[1]])
print(s(None), [])
Runtime: 74 ms, faster than 10.45% of Python3 online submissions for Binary Tree Level Order Traversal. Memory Usage: 14.2 MB, less than 84.74% of Python3 online submissions for Binary Tree Level Order Traversal.