给定一个二叉树, 返回其节点值自底向上的层次遍历. (即按从叶子节点所在层到根节点所在的层, 逐层从左向右遍历)
例如:
给定二叉树 [3,9,20,null,null,15,7],
- 3
- / \
- 9 20
- / \
- 15 7
返回其自底向上的层次遍历为:
- [
- [15,7],
- [9,20],
- [3]
- ]
算法: 与层次遍历类似, 我们只需最后 reverse 一下即可.
- /**
- * 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:
- vector<int> getval(vector<TreeNode*> u){
- vector<int>path;
- for(auto x:u)
- path.push_back(x->val);
- return path;
- }
- vector<vector<int>> levelOrderBottom(TreeNode* root) {
- vector<vector<int>>ans;
- if(!root)return ans;
- vector<TreeNode*>level;
- level.push_back(root);
- ans.push_back(getval(level));
- while(true){
- vector<TreeNode*>nl;
- for(auto u:level){
- if(u->left)nl.push_back(u->left);
- if(u->right)nl.push_back(u->right);
- }
- if(nl.size()){
- ans.push_back(getval(nl));
- level=nl;
- }
- else
- break;
- }
- reverse(ans.begin(),ans.end());
- return ans;
- }
- };
来源: http://www.bubuko.com/infodetail-3119772.html