Binary Tree Level Order Traversal

Problem: Binary Tree Level Order Traversal

Breadth-first search is a perfect solution for level order traversal. Different from other breadth-first search problems, we need depth or level information in this one. So we use two lists to maintain current level and next level and replace current one with next after dealing with current one.

Code in Python:

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        level, ans = [], []
        if root: level.append(root)
        while level:
            nextLevel, currentLevel = [], []
            for node in level:
                currentLevel.append(node.val)
                if node.left: nextLevel.append(node.left)
                if node.right: nextLevel.append(node.right)
            ans.append(currentLevel)
            level = nextLevel
        return ans