# Binary Tree Level Order Traversal

## Question

### Problem Statement

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

#### Example

Given binary tree {3,9,20,#,#,15,7},

    3
/ \
9  20
/  \
15   7


return its level order traversal as:

[
[3],
[9,20],
[15,7]
]


#### Challenge

Challenge 1: Using only 1 queue to implement it.

Challenge 2: Use DFS algorithm to do it.

## 题解 - 使用队列

### C++

/**
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/

class Solution {
/**
* @param root: The root of binary tree.
* @return: Level order a list of lists of integer
*/
public:
vector<vector<int> > levelOrder(TreeNode *root) {
vector<vector<int> > result;

if (NULL == root) {
return result;
}

queue<TreeNode *> q;
q.push(root);
while (!q.empty()) {
vector<int> list;
int size = q.size(); // keep the queue size first
for (int i = 0; i != size; ++i) {
TreeNode * node = q.front();
q.pop();
list.push_back(node->val);
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
result.push_back(list);
}

return result;
}
};


### Java

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (root == null) return result;

q.offer(root);
while (!q.isEmpty()) {
List<Integer> list = new ArrayList<Integer>();
int qSize = q.size();
for (int i = 0; i < qSize; i++) {
TreeNode node = q.poll();
// push child node into queue
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
}

return result;
}
}


### 源码分析

1. 异常，还是异常
2. 使用STL的queue数据结构，将root添加进队列
3. 遍历当前层所有节点，注意需要先保存队列大小，因为在入队出队时队列大小会变化
4. list保存每层节点的值，每次使用均要初始化