难度:Easy
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
例如:给定二叉树 [3,9,20,null,null,15,7],3/ \9 20/ \15 7返回其自底向上的层次遍历为:[[15,7],[9,20],[3]]
类似于429题的N叉树的层次遍历。代码如下:
/*** 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<vector<int>> levelOrderBottom(TreeNode* root) {deque<TreeNode*> dt;vector<vector<int>> res;if(!root) return res;dt.push_back(root);while(!dt.empty()){vector<int> tmp;for(auto i:dt)tmp.push_back(i->val);int len=dt.size();while(len--){if(dt[0]->left)dt.push_back(dt[0]->left);if(dt[0]->right)dt.push_back(dt[0]->right);dt.pop_front();}// cout<<dt.size()<<endl;res.push_back(tmp);}reverse(res.begin(),res.end());return res;}};