Binary Tree Level Order Traversal II
Desicription
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,null,null,15,7]
,
return its bottom-up level order traversal as:
1 2 3 4 5
| [ [15,7], [9,20], [3] ]
|
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
|
class Solution { private: vector<vector<int>> res; void searchTree(TreeNode* root, int level) { if(!root) return ; if(level == res.size()) res.push_back(vector<int>()); res[level].push_back(root->val); searchTree(root->left, level+1); searchTree(root->right, level+1); } public: vector<vector<int>> levelOrderBottom(TreeNode* root) { searchTree(root, 0); for(int i = 0, j = res.size()-1; i <= j; i++, j--) swap(res[i], res[j]); return res; } };
|