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; }