# One of C++ solutions (preorder)

• ``````vector<vector<int>> ret;

void buildVector(TreeNode *root, int depth)
{
if(root == NULL) return;
if(ret.size() == depth)
ret.push_back(vector<int>());

ret[depth].push_back(root->val);
buildVector(root->left, depth + 1);
buildVector(root->right, depth + 1);
}

vector<vector<int> > levelOrder(TreeNode *root) {
buildVector(root, 0);
return ret;
}``````

• i wonder what's this means? ret.push_back(vector<int>( ) );

• Great solution! Doesn't use extra space for a queue like other implementations. Also funny how the problem is called Level Order Traversal, but you used preorder and it still worked. Really thinking outside the box there.

• Nice. But call stack of recursive method should be considered as extra space, too.

for very 'lean' tree (most non-leaf node have only one child), this dfs appoach consume O(n) memory, while bfs approach with queue cost almost constant space.
for near complete tree (most non-leaf node have two child), dfs approach cost O(log(n)) memory, whereas bfs approach cost O(n) memory

• good solution!

• It is the initialization of each level

• nice job about comparing ret size with depth. I was also thinking using recursion, but gave up to iteration

• Brilliant!! However, sometimes really don't know how to design the recursion solution...

• Nice solution, I really like this part: if(ret.size() == depth)

• Thank you for your comment

• Very nice code. But why it is wrong if I change

``````if(ret.size() == depth)
ret.push_back(vector<int>());
``````

to

``````if(depth > ret.size() - 1)
ret.push_back(vector<int>());
``````

• @haoranc this has something to do with the subtraction of unsigned int and signed int. Change it to
if(depth>(int)(ret.size()-1)) should solve the problem

• @nilath Cool, I had the same idea . it's sort of dfs , although the exercise itself points very much to the direction of bfs.

• @tyk This means constructing an empty vector as the d-th(depth) element of the 2-d vector ret.

• vector<int>();mean:

• Why do we have to use initialize the returning vector globally? Tried returning the vector recursively and it didn't work.

• @mithun96 If you don't want to use global variable, you can put the vector inside the function as a parameter:

``````    void buildVector(TreeNode *root, int depth,vector<vector<int>> & ret)
{
if(root == NULL) return;
if(ret.size() == depth)
ret.push_back(vector<int>());

ret[depth].push_back(root->val);
buildVector(root->left, depth + 1, ret);
buildVector(root->right, depth + 1, ret);
}

vector<vector<int> > levelOrder(TreeNode *root) {
vector<vector<int>> ret;
buildVector(root, 0, ret);
return ret;
}
``````

• @daxietx why to push_back vector<int>() to ret?
if(ret.size() == depth)
ret.push_back(vector<int>());

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.