> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/wan-quan-an-zhao-jiu-zhang-suan-fa-shua-de-60-dao-zuo-you/iii.-binary-tree/102.-binary-tree-level-order-traversal.md).

# 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.

{% tabs %}
{% tab title="Java(Iteration)" %}

```java
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;
    }
}
```

{% endtab %}

{% tab title="Java(Recursive)" %}

```java
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);
    }
}
```

{% endtab %}

{% tab title="Python" %}

```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
```

{% endtab %}
{% endtabs %}