102. Binary Tree Level Order Traversal

# Medium, BFS

BFS-宽度优先搜索遍历二叉树

1. 2 Queues

2. 1 Queue + Dummy node

3. 1 Queue( best )

Solution 3: 1 Queue

Record size of each level, then do for-loop. Two inner loops.

Java(Iteration)

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(root == null) return res;
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while( !queue.isEmpty() ) {
            List<Integer> level = new ArrayList<Integer>();
            int l = queue.size();
            while(l > 0) {
                root = queue.poll();
                if(root.left != null) queue.add(root.left);
                if(root.right != null) queue.add(root.right);
                l --;
                level.add(root.val);
            }
            res.add(level);
        }
        
        return res;
    }
}

Java(Recursive)

class Solution {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null) return res;
        helper(root, 0);
        return res;
    }
    
    public void helper(TreeNode node, int level) {
        if(res.size() == level)
            res.add(new ArrayList<Integer>());
        
        res.get(level).add(node.val);
        if(node.left != null) helper(node.left, level + 1);
        if(node.right != null) helper(node.right, level + 1);
    }
}

Python

# 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]]:
        queue = []
        result = []
        # consider edge case
        if root == None:
            return []
        
        # regular case
        queue.append(root)
        while len(queue) != 0:
            length = len(queue)
            level = []
            for i in range(0, length):
                root = queue.pop(0)
                level.append(root.val)
                if root.left != None:
                    queue.append(root.left)
                if root.right != None:
                    queue.append(root.right)
            result.append(level)
                
        return resulttab