题目
二叉树的锯齿形层次遍历
给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:[[3],[20,9],[15,7]]
示例 2:
输入:root = [1]
输出:[[1]]
示例 3:
输入:root = []
输出:[]
提示:
树中节点数目在范围 [0, 2000] 内
-100 <= Node.val <= 100
答案
/**
-
Definition for a binary tree node.
-
struct TreeNode {
-
int val;
-
TreeNode *left;
-
TreeNode *right;
-
TreeNode() : val(0), left(nullptr), right(nullptr) {}
-
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
-
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
-
};
/
class Solution {
public:
vector<vector> zigzagLevelOrder(TreeNode root) {
vector<vector> res;
if(root == nullptr){
return res;
}
queue<TreeNode*> q;vector
level;
q.push(root);
bool reverse_flag = false;
while(!q.empty()){
int size = q.size();
vectorlevel;
for(int i=0;i<size;i++){
auto f = q.front();
level.push_back(f->val);
if(f->left) q.push(f->left);
if(f->right) q.push(f->right);
q.pop();
}
if(reverse_flag) reverse(level.begin(),level.end());
reverse_flag = !reverse_flag;
res.push_back(level);}
return res;
}
};
关键
关键在于需要记录当前
标签:right,TreeNode,11.9,level,int,算法,root,left From: https://www.cnblogs.com/minipython-wldx/p/17819321.html