给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
例如:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回锯齿形层次遍历如下:
[
[3],
[20,9],
[15,7]
]
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if(root == NULL)
return {};
queue<TreeNode*> q;
TreeNode *tp;
q.push(root);
vector<int> lv;
vector<vector<int>> ans;
int n, depth = 0;
while(!q.empty())
{
n = q.size();
while(n--)
{
tp = q.front();
q.pop();
lv.push_back(tp->val);
if(tp->left)
q.push(tp->left);
if(tp->right)
q.push(tp->right);
}
depth++;
if(depth%2 == 0)//对相应的层,进行反转
reverse(lv.begin(),lv.end());
ans.push_back(lv);
lv.clear();
}
return ans;
}
};
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if(root == NULL)
return {};
stack<TreeNode*> l, r;
TreeNode *tp;
l.push(root);
vector<int> lv;
vector<vector<int>> ans;
while(!l.empty() || !r.empty())
{
while(!l.empty())
{
tp = l.top();
l.pop();
lv.push_back(tp->val);
if(tp->left)
r.push(tp->left);
if(tp->right)
r.push(tp->right);
}
if(!lv.empty())
{
ans.push_back(lv);
lv.clear();
}
while(!r.empty())
{
tp = r.top();
r.pop();
lv.push_back(tp->val);
if(tp->right)
l.push(tp->right);
if(tp->left)
l.push(tp->left);
}
if(!lv.empty())
{
ans.push_back(lv);
lv.clear();
}
}
return ans;
}
};