class Solution {
public:
vector<vector<int> > levelOrder(TreeNode *root) {
vector<vector<int> > result;
if (!root) return result;
queue<TreeNode*> q;
q.push(root);
q.push(NULL);
vector<int> cur_vec;
while(!q.empty()) {
TreeNode* t = q.front();
q.pop();
if (t==NULL) {
result.push_back(cur_vec);
cur_vec.resize(0);
if (q.size() > 0) {
q.push(NULL);
}
} else {
cur_vec.push_back(t>val);
if (t>left) q.push(t>left);
if (t>right) q.push(t>right);
}
}
return result;
}
};
C++ solution using only one queue / use a marker NULL


Can I ask why push_back(cur_vec) when t==NULL? I understand that for each level cur_vec needs to be push_back in the result. But it does not seem to me that the path terminator in the binary tree serialization is equivalent to the end of the current level? Am I missing something? thanks.

@pankit why not
vector<vector<int>> levelOrder1(TreeNode* root) { vector<vector<int>> res; if (!root) return res; queue<TreeNode*> level_node; level_node.push(root); while (!level_node.empty()) { vector<int> level_val; auto sz = level_node.size(); for (decltype(sz) i = 0; i < sz; ++i) { TreeNode *node = level_node.front(); level_node.pop(); level_val.push_back(node>val); if (node>left) level_node.push(node>left); if (node>right) level_node.push(node>right); } res.push_back(level_val); } return res; }


@xiaonimo Agree. It is unnecessary to insert a NULL to keep track of the end of every level.

I think the advantage of using NULL as sentinel of end of level here is you can forget about the size of elements in queue or you don't need to count how many node you visited in this level to detect the end of each level. Getting a single NULL means you reach the end of each level; getting 2 consequent NULLs means you finish the traversal.
class Solution {
public:
vector<vector<int> > levelOrder(TreeNode *root) {
vector<vector<int> > res;
vector<int> line;
TreeNode *prev = NULL, *curr = NULL;queue<TreeNode*> Q; Q.push(root); Q.push(NULL); while (true) { curr = Q.front(); Q.pop(); if (NULL != prev) { line.push_back(prev>val); } if (NULL == curr) { if (NULL == prev) { // Traversal completed. break; } else { // Reaches the end of each level. Q.push(NULL); res.push_back(line); line.clear(); } } else { if (curr>left) { Q.push(curr>left); } if (curr>right) { Q.push(curr>right); } } prev = curr; } return res; }
};

Same idea with C++ 11.
vector<vector<int>> levelOrder(TreeNode* root) { std::vector<std::vector<int>> values; if (root == nullptr) return values; std::queue<TreeNode*> q; q.push(root); q.push(nullptr); // a flag indicating the end of a level values.push_back(std::vector<int>()); while (true){ auto p = q.front(); q.pop(); if (p == nullptr){ // a level is finished if (q.empty()) // no more levels, ending of the tree break; q.push(nullptr); // the ith level is poped completely, then we can add the nullptr for the (i+1)th level values.push_back(std::vector<int>()); // to store the values of the next level }else{ values.back().push_back(p>val); if (p>left != nullptr) q.push(p>left); if (p>right != nullptr) q.push(p>right); } } return values; }

@faustlin consider NULL as a mark which indicates a level ends here. Every time you meet a NULL, you must have put the nodes of this level into the vector, and all the children of them into the queue. So here cur_vec has all nodes of this level and you need to store it in result. Then you put another NULL into the queue to mark the end of the next level.

My 3ms solution use deque.
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> ret; if (root == NULL){ return ret; } deque<TreeNode*> q; q.push_back(root); int next = 1; //record how many elements should be poped in next level while(1){ vector<int> v; int cflag = 0; int nnext = 0; int qsize = q.size(); for(int i = 0; i < qsize; i++){ if(q[i] != NULL){ //if all elements in queue are null, break; cflag = 1; } if(cflag == 1){ for(int i = 0; i < next; i++){ TreeNode * f = q.front(); if(f != NULL){ v.push_back(f>val); q.pop_front(); q.push_back(f>left); q.push_back(f>right); nnext += 2; }else{ q.pop_front(); } } }else{ break; } ret.push_back(v); next = nnext; } return ret; } };