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;
}
One of C++ solutions (preorder)


there are tradeoffs,
for very 'lean' tree (most nonleaf 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 nonleaf node have two child), dfs approach cost O(log(n)) memory, whereas bfs approach cost O(n) memory

@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 dth(depth) element of the 2d vector ret.

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