Leetcode 103. 二叉树的锯齿形层序遍历

题目描述

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],

1
2
3
4
5
6
7
8
9
10
11
12
    3
   / \
  9  20
    / \
   15  7
返回锯齿形层序遍历如下：

[
  [3],
  [20,9],
  [15,7]
]

解题思路

这道题是二叉树层次遍历的变种，可以参照二叉树遍历大总结里面的层次遍历中的方法进行微改动。

由于我们已经加上了level来指示二叉树的层数，那么我们其实只要判断level为奇数的时候，将存储那一层结点值的vector颠倒再加入两层vector就可以了

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void levelOrder(TreeNode* root,vector<vector<int>>&res,int lev)
{
    if(root==nullptr) return ;
    queue<TreeNode*>q;
    q.push(root);
    while(!q.empty())
    {
        int size=q.size();
        vector<int>level;
        for(int i=0;i<size;i++)
        {
            TreeNode* node=q.front();
            q.pop();
            if(node==nullptr) continue;
            level.push_back(node->val);
            q.push(node->left);
            q.push(node->right);
        }
        if(lev%2==1) reverse(level.begin(),level.end());
        lev++;
        if(level.size()>0) res.push_back(level);

    }
}
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>>res;
    levelOrder(root,res,0);
    return res;


}