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],
The result will be
[
[3],
[9,20],
[15,7]
]
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> q;
queue<int> level;
q.push(root);
level.push(1);
int levelCount = 1;
vector<vector<int>> result;
vector<int> res;
while(!q.empty()){
int curLevel = level.front();
level.pop();
TreeNode* curNode = q.front();
q.pop();
if(curLevel != levelCount){
levelCount = curLevel;
result.push_back(res);
res.clear();
}
if(curNode != NULL){
res.push_back(curNode -> val);
q.push(curNode -> left);
q.push(curNode -> right);
level.push(levelCount + 1);
level.push(levelCount + 1);
}
}
return result;
}