[LeetCode] 102. Binary Tree Level Order Traversal

Problem : https://leetcode.com/problems/binary-tree-level-order-traversal/

Use BFS to traverse the given binary tree.

# 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: TreeNode) -> List[List[int]]:
        
        if not root:
            return []
        
        result = [] 
        queue = deque([root])
        
        # bfs
        while queue:
            level = deque()
            result.append([])
            
            while queue:
                node = queue.popleft()
                
                result[-1].append(node.val)
                
                if node.left:
                    level.append(node.left)
                    
                if node.right:
                    level.append(node.right)
            
            queue = level
        
        return result

Recursive DFS solution:

# 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: TreeNode) -> List[List[int]]:
        def dfs(level, node):
            if node:
                yield (level, node.val)
                yield from dfs(level + 1, node.left)
                yield from dfs(level + 1, node.right)
        
        result = []
        
        for level, val in dfs(0, root):
            if level >= len(result):
                result.append([val])
            else:
                result[level].append(val)
        
        return result

Iterative DFS solution:

# 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: TreeNode) -> List[List[int]]:
        result = []
        
        stack = [(0, root)] if root else []
        
        while stack:
            level, node = stack.pop()
            
            if level >= len(result):
                result.append([node.val])
            else:
                result[level].append(node.val)
        
            if node.right:
                stack.append((level + 1, node.right))
            
            if node.left:
                stack.append((level + 1, node.left))
            
        return result

Edited on 04/21/2021. Add resursive and iterative DFS solution.