YunheWang0813
3/6/2020 - 8:11 PM

## 0102. Binary Tree Level Order Traversal

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res;
queue<TreeNode*> Q;
Q.push(root);
while (!Q.empty()) {
int n = Q.size();
vector<int> v;
for (int i = 0; i < n; i++) {
TreeNode* p = Q.front(); Q.pop();
v.push_back(p -> val);
if (p -> left) Q.push(p -> left);
if (p -> right) Q.push(p -> right);
}
res.push_back(v);
}
return res;
}
};

What: BFS

Why: Level Order

## Solve

Idea: Calculate the size of Queue and create vector which consists the nodes of the same level in the tree.

Be careful:

1. Need to push the temporal vector to res before getting out of while loop

## Complexity

Time: O(N), since each node is processed exactly once.

Space: O(N), to keep the output structure which contains N node values.

1. 7