NC224. 从下到上打印二叉树
描述
给定一棵二叉树，返回齐自底向上的层序遍历。
数据范围：二叉树上节点数满足 
，二叉树上的值满足 
样例图：
示例1
输入:
{1,2,3,4,#,5,6}
输出:
[[4,5,6],[2,3],[1]]
说明:
如题面图示示例2
输入:
{1,2}
输出:
[[2],[1]]
NC224. 从下到上打印二叉树
描述
示例1
输入:
{1,2,3,4,#,5,6}
输出:
[[4,5,6],[2,3],[1]]
说明:
如题面图示示例2
输入:
{1,2}
输出:
[[2],[1]]
C++ 解法, 执行用时: 2ms, 内存消耗: 424KB, 提交时间: 2022-02-08
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/*
方法一：层序遍历
最后将输出结果逆序即可
*/
vector<vector<int> > levelOrderBottom(TreeNode* root) {
vector<vector<int>> v;
queue<TreeNode*>q;
if (root) q.emplace(root);
while (!q.empty()) {
vector<int>v1;
int len = q.size();
for (int i = 0; i< len; ++i) {
TreeNode* cur = q.front();
q.pop();
if (cur->left)q.emplace(cur->left);
if (cur->right)q.emplace(cur->right);
v1.emplace_back(cur->val);
}
v.emplace_back(v1);
}
reverse(v.begin(), v.end());
return v;
}
/*
同方法一，利用栈 - 超内存
用栈接住层次遍历每一层的一维数组结果，然后再弹栈形成最终要返回的二维数组结果
*/
vector<vector<int> > levelOrderBottom1(TreeNode* root) {
stack<vector<int>> stack;
queue<TreeNode*> queue;
queue.push(root);
while(!queue.empty()){
int queueSize = queue.size();
vector<int> layer(queueSize);
for(int i = 0; i < queueSize; i++){
TreeNode* node = queue.front();
layer[i] = node->val;
if(node->left != NULL){
queue.push(node->left);
}
if(node->right != NULL){
queue.push(node->right);
}
}
stack.push(layer);
}
int row = 0;
vector<vector<int>> res(stack.size(), vector<int>());
while(!stack.empty()) {
res[row] = stack.top(); stack.pop();
row ++;
}
return res;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-04-06
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型vector<vector<>>
*/
vector<vector<int> > levelOrderBottom(TreeNode* root) {
stack<vector<int>>st;
TreeNode*p=root;
int layer=1;
queue<pair<TreeNode*,int>>q;
q.push({root,layer});
vector<int>vec;
vector<vector<int>>result;
while(!q.empty()){
auto front=q.front();
q.pop();
if(front.second==layer){
vec.emplace_back(front.first->val);
}
else{
result.emplace_back(vec);
layer++;
vec=vector<int>{front.first->val};
}
if(front.first->left){
q.push({front.first->left,layer+1});
}
if(front.first->right){
q.push({front.first->right,layer+1});
}
}
result.emplace_back(vec);
reverse(result.begin(),result.end());
return result;// write code here
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 408KB, 提交时间: 2022-06-08
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型vector<vector<>>
*/
vector<vector<int> > levelOrderBottom(TreeNode* root) {
queue<TreeNode*> que;
if (root != nullptr) {
que.push(root);
}
vector<vector<int>> res;
while (!que.empty()) {
int size = que.size();
vector<int> vec;
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
res.push_back(vec);
}
reverse(res.begin(), res.end());
return res;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 408KB, 提交时间: 2022-02-19
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型vector<vector<>>
*/
vector<vector<int> > levelOrderBottom(TreeNode* root) {
// write code here
vector<vector<int> > res;
if(!root) return res;
queue<TreeNode*> que;
que.push(root);
vector<int> vet;
while(!que.empty())
{
int n = que.size();
for(int i=0;i<n;i++)
{
TreeNode* p = que.front();
que.pop();
vet.push_back(p->val);
if(p->left) que.push(p->left);
if(p->right) que.push(p->right);
}
res.push_back(vet);
vet.clear();
}
reverse(res.begin(), res.end());
return res;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 416KB, 提交时间: 2022-05-08
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型vector<vector<>>
*/
vector<vector<int> > levelOrderBottom(TreeNode* root) {
// write code here
vector<vector<int>> res;
queue<pair<TreeNode*,int>> que;
que.push(pair<TreeNode*,int>(root,0));
while(que.size()>0){
pair<TreeNode*,int> front = que.front();
if(res.size()<=front.second)
res.push_back(vector<int>{});
if(que.front().first->left!=NULL)
que.push(pair<TreeNode*,int>(front.first->left,front.second+1));
if(que.front().first->right!=NULL)
que.push(pair<TreeNode*,int>(front.first->right,front.second+1));
res.back().push_back(front.first->val);
que.pop();
}
return vector<vector<int>>(res.rbegin(),res.rend());
}
};