# 102. Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
Example:
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
# Solution
Approach 1: BFS.
Approach 2: DFS.
# Code (Python)
Approach 1:
from collections import deque
class Solution:
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
result = []
queue = deque([[root]])
while queue:
level = queue.popleft()
level_result = []
next_level_nodes = []
for node in level:
level_result.append(node.val)
if node.left:
next_level_nodes.append(node.left)
if node.right:
next_level_nodes.append(node.right)
result.append(level_result)
if next_level_nodes:
queue.append(next_level_nodes)
return result
# Code (C++)
Approach 1:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
// BFS.
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
queue<TreeNode*> q;
if (root)
q.push(root);
while (!q.empty())
{
int qSize = q.size();
vector<int> buf;
for (int i = 0; i < qSize; ++i)
{
TreeNode *curr = q.front();
q.pop();
buf.push_back(curr->val);
if (curr->left)
q.push(curr->left);
if (curr->right)
q.push(curr->right);
}
if (buf.size() > 0)
res.push_back(buf);
}
return res;
}
};
Approach 2:
// DFS.
class Solution {
private:
vector<vector<int>> res;
void doLevelOrder(TreeNode *root, int level) {
if (root == NULL)
return;
if (res.size() < level)
res.push_back(vector<int>());
res[level-1].push_back(root->val);
doLevelOrder(root->left, level + 1);
doLevelOrder(root->right, level + 1);
}
public:
vector<vector<int>> levelOrder(TreeNode* root) {
doLevelOrder(root, 1);
return res;
}
};