Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7]
[9,20],
[3],
]
BFS solution:
vector<vector<int> > levelOrderBottom(TreeNode *root) {
vector<vector<int> > ret;
if(root == NULL)
return ret;
vector<TreeNode *> level;
level.push_back(root);
while(true) {
if(level.size() == )
break;
vector<int> nums;
vector<TreeNode *> tmp;
for(auto item : level) {
nums.push_back(item->val);
if(item->left != NULL)
tmp.push_back(item->left);
if(item->right != NULL)
tmp.push_back(item->right);
}
ret.insert(ret.begin(), nums);
level = tmp;
}
return ret;
}DFS solution:
void getLevelNums(TreeNode *root, vector<vector<int> > &ret, int level) {
if(ret.size() < level + ){
vector<int> nums;
nums.push_back(root->val);
ret.insert(ret.begin(), nums);
}else if (ret.size() >= level + ) {
ret[ret.size() - level - ].push_back(root->val);
}
if(root->left != NULL)
getLevelNums(root->left, ret, level + );
if(root->right != NULL)
getLevelNums(root->right, ret, level + );
}
vector<vector<int> > levelOrderBottom(TreeNode *root) {
vector<vector<int> > ret;
if(root == NULL)
return ret;
getLevelNums(root, ret, );
return ret;
}