# LeetCode – Binary Tree Level Order Traversal Solution

### 题目：

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

For example:
Given binary tree `[3,9,20,null,null,15,7]`,

```    3
/ \
9  20
/  \
15   7
```

return its level order traversal as:

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

### 解题：

两种方式处理， 广度优先搜索借助队列，一层一层处理，并放入二维数组； 深度优先搜索借助栈， 一个一个处理， 将每一个元素方式所属层对应的一维数组中。

### 实现：

• BFS  使用队列实现

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {

vector<vector<int>> result;

if (!root) {
return result;
}

queue<TreeNode*> q;
q.push(root);

while (!q.empty()){

vector<int> current;
int level_size = q.size();

for (int i=0; i<level_size; i++){
TreeNode* node = q.front();
q.pop();
current.push_back(node->val);

if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}

result.push_back(current);

}

return result;
}
};``````

### 实现：

• DFS    递归实现：
``````class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
if (!root){
return result;
}
result = _dfs(root, 0, result);
return result;
}

vector<vector<int>> _dfs(TreeNode *node, int level, vector<vector<int>> &res){
if (!node){
return res;
}
if (res.size() < level+1){
res.push_back({});
}
res[level].push_back(node->val);
_dfs(node->left, level+1, res);
_dfs(node->right, level+1, res);

return res;
}
};``````