LeetCode 103. 二叉树的锯齿形层次遍历（双端队列+BFS）_leetcode 103 双端队列

1.题目

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

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

    3
   / \
  9  20
    /  \
   15   7
返回锯齿形层次遍历如下：

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2.题解

双端队列

class Solution
{
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root)
    {
        vector<vector<int>> ans;
        if (!root) return ans;
        deque<TreeNode*> q;
        q.push_back(root);
        bool flag = true;
        TreeNode* tmp;
        while (!q.empty())
        {
            int Size = q.size();
            vector<int> tmp_vec;
            while (Size)
            {
                if (flag)
                {
                    //前取后放
                    tmp = q.front();
                    q.pop_front();
                    if (tmp->left) q.push_back(tmp->left);
                    // 下一层顺序存放至尾
                    if (tmp->right) q.push_back(tmp->right);
                }
                else
                {
                    // 后取前放
                    tmp = q.back();
                    q.pop_back();
                    if (tmp->right) q.push_front(tmp->right);
                    // 下一层逆序存放至首
                    if (tmp->left) q.push_front(tmp->left);
                }
                tmp_vec.push_back(tmp->val);
                --Size;
            }
            flag = !flag;
            ans.push_back(tmp_vec);
        }
        return ans;
    }
};



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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

参考：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/solution/c-shuang-duan-dui-lie-ji-bai-100-by-karlzhang/