- 首页 > it技术 > >
107.|107. 二叉树的层次遍历 II
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)例如:
给定二叉树 [3,9,20,null,null,15,7],3
/ \
920
/\
157
返回其自底向上的层次遍历为:[
[15,7],
[9,20],
[3]
]
class Solution {
public:
vector> levelOrderBottom(TreeNode* root) {
vector> res;
if(root==NULL)
return res;
TreeNode* temp;
int psize=1;
int childsize=0;
queue q;
q.push(root);
vector q_val;
do
{
temp=q.front();
q_val.push_back(temp->val);
q.pop();
if(temp->left)//根据父节点个数,每次把同一层的左右子节点入队
{
q.push(temp->left);
childsize++;
}
if(temp->right)
{
q.push(temp->right);
childsize++;
}
psize--;
//父节点减一
if(psize==0)//遍历了一层
{
res.push_back(q_val);
q_val.clear();
psize=childsize;
childsize=0;
}}while(!q.empty());
reverse(res.begin(),res.end());
return res;
}
};
推荐阅读