vector<vector<int> > levelOrder(TreeNode *root) {
vector<vector<int> > retVal;
levelOrder(root, retVal, 0);
reverse(retVal.begin(), retVal.end());
return retVal;
}
void levelOrder(TreeNode* root, vector<vector<int> > &v, int currLevel) {
if (root == NULL) {
return;
}
if (v.empty()  currLevel > (v.size()  1)) {
v.push_back(vector<int>());
}
v[currLevel].push_back(root>val);
levelOrder(root>left, v, currLevel + 1);
levelOrder(root>right, v, currLevel + 1);
}
My Neat Solution in C++


The following code without reversing too slow (60 ms) because insert operation on vector that too at beginning will be too costly. I wonder if there's any other way that doesn't involve reversing or inserting at front.
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: void levelOrderBottomRecur(TreeNode *root, int level,vector<vector<int> > &result){ if(root==NULL) return; if(level>=result.size()) result.insert(result.begin(),vector<int>()); result[result.size()level1].push_back(root>val); levelOrderBottomRecur(root>left,level+1,result); levelOrderBottomRecur(root>right,level+1,result); } vector<vector<int>> levelOrderBottom(TreeNode* root) { vector<vector<int> > result; levelOrderBottomRecur(root,0,result); return result; } };

@weijiang2009 8ms
vector<vector<int>> levelOrderBottom(TreeNode* root) { vector<vector<int>> res; if (!root) { return res; } queue<TreeNode*> t; t.push(root); while (!t.empty()) { vector<int> tn; int cnt = t.size(); for (unsigned int i = 0; i < cnt; ++i) { TreeNode *cur = t.front(); tn.push_back(cur>val); t.pop(); if (cur>left) t.push(cur>left); if (cur>right) t.push(cur>right); } //do not use insert() here,it cost too much time. //use reverse() insteadly res.push_back(tn); } reverse(res.begin(), res.end()); return res; }


@jaegerstar
v
is only smaller than level the first time that level is getting populated. After going left, the right node would be stored in the same level. So in that case, you don't need to push_back() an empty vector.

A few points:
(1) v is empty at declaration
(2) elements of v should be "push_back" when reaching a new deep level ever reached
(3) at some recursion step, level+1 can be smaller than size of v, for example:for the following tree:
level 0: 1
level 1: 2 3
level 2: 4when it comes to node 3, node 2,4 have already been visited, size of v is 3. But when it comes to 2, it is the first time reaching level 1, but now v only have 1 element for level 0, so have to push_back another element for this level 2.