Binary Tree Level Order Traversal II
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], ]
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int> > out; void levelTraval(vector<TreeNode* >& level) { if(level.size() > 0) { vector<TreeNode*> nextLevel; for(int i = 0; i < level.size(); i++) { if(level[i]->left) nextLevel.push_back(level[i]->left); if(level[i]->right) nextLevel.push_back(level[i]->right); } levelTraval(nextLevel); vector<int> val; for(int i = 0; i < level.size(); i++) val.push_back(level[i]->val); out.push_back(val); } } vector<vector<int> > levelOrderBottom(TreeNode *root) { // Start typing your C/C++ solution below // DO NOT write int main() function out.clear(); vector<TreeNode*> v; if(root != NULL) { v.push_back(root); levelTraval(v); } return out; } };