给你二叉树的根节点 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
📺 视频题解
📖 文字题解
方法一：广度优先遍历
此题是「102. 二叉树的层序遍历 」的变种，最后输出的要求有所变化，要求我们按层数的奇偶来决定每一层的输出顺序。规定二叉树的根节点为第 $0$ 层，如果当前层数是偶数，从左至右输出当前层的节点值，否则，从右至左输出当前层的节点值。
我们依然可以沿用第 102 题的思想，修改广度优先搜索，对树进行逐层遍历，用队列维护当前层的所有元素，当队列不为空的时候，求得当前队列的长度 $\textit{size}$，每次从队列中取出 $\textit{size}$ 个元素进行拓展，然后进行下一次迭代。
为了满足题目要求的返回值为「先从左往右，再从右往左」交替输出的锯齿形，我们可以利用「双端队列」的数据结构来维护当前层节点值输出的顺序。
双端队列是一个可以在队列任意一端插入元素的队列。在广度优先搜索遍历当前层节点拓展下一层节点的时候我们仍然从左往右按顺序拓展，但是对当前层节点的存储我们维护一个变量 $\textit{isOrderLeft}$ 记录是从左至右还是从右至左的：
当遍历结束的时候我们就得到了答案数组。
<,,,,,,,,,,,>
[sol1-C++]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
| class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (!root) {
return ans;
}
queue<TreeNode*> nodeQueue;
nodeQueue.push(root);
bool isOrderLeft = true;
while (!nodeQueue.empty()) {
deque<int> levelList;
int size = nodeQueue.size();
for (int i = 0; i < size; ++i) {
auto node = nodeQueue.front();
nodeQueue.pop();
if (isOrderLeft) {
levelList.push_back(node->val);
} else {
levelList.push_front(node->val);
}
if (node->left) {
nodeQueue.push(node->left);
}
if (node->right) {
nodeQueue.push(node->right);
}
}
ans.emplace_back(vector<int>{levelList.begin(), levelList.end()});
isOrderLeft = !isOrderLeft;
}
return ans;
}
};
|
[sol1-Java]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
| class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ans = new LinkedList<List<Integer>>();
if (root == null) {
return ans;
}
Queue<TreeNode> nodeQueue = new ArrayDeque<TreeNode>();
nodeQueue.offer(root);
boolean isOrderLeft = true;
while (!nodeQueue.isEmpty()) {
Deque<Integer> levelList = new LinkedList<Integer>();
int size = nodeQueue.size();
for (int i = 0; i < size; ++i) {
TreeNode curNode = nodeQueue.poll();
if (isOrderLeft) {
levelList.offerLast(curNode.val);
} else {
levelList.offerFirst(curNode.val);
}
if (curNode.left != null) {
nodeQueue.offer(curNode.left);
}
if (curNode.right != null) {
nodeQueue.offer(curNode.right);
}
}
ans.add(new LinkedList<Integer>(levelList));
isOrderLeft = !isOrderLeft;
}
return ans;
}
}
|
[sol1-JavaScript]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
| var zigzagLevelOrder = function(root) {
if (!root) {
return [];
}
const ans = [];
const nodeQueue = [root];
let isOrderLeft = true;
while (nodeQueue.length) {
let levelList = [];
const size = nodeQueue.length;
for (let i = 0; i < size; ++i) {
const node = nodeQueue.shift();
if (isOrderLeft) {
levelList.push(node.val);
} else {
levelList.unshift(node.val);
}
if (node.left !== null) {
nodeQueue.push(node.left);
}
if (node.right !== null) {
nodeQueue.push(node.right);
}
}
ans.push(levelList);
isOrderLeft = !isOrderLeft;
}
return ans;
};
|
[sol1-Golang]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
| func zigzagLevelOrder(root *TreeNode) (ans [][]int) {
if root == nil {
return
}
queue := []*TreeNode{root}
for level := 0; len(queue) > 0; level++ {
vals := []int{}
q := queue
queue = nil
for _, node := range q {
vals = append(vals, node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
if level%2 == 1 {
for i, n := 0, len(vals); i < n/2; i++ {
vals[i], vals[n-1-i] = vals[n-1-i], vals[i]
}
}
ans = append(ans, vals)
}
return
}
|
[sol1-C]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
| #define N 2000
int** zigzagLevelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
*returnSize = 0;
if (root == NULL) {
return NULL;
}
int** ans = malloc(sizeof(int*) * N);
*returnColumnSizes = malloc(sizeof(int) * N);
struct TreeNode* nodeQueue[N];
int left = 0, right = 0;
nodeQueue[right++] = root;
bool isOrderLeft = true;
while (left < right) {
int levelList[N * 2];
int front = N, rear = N;
int size = right - left;
for (int i = 0; i < size; ++i) {
struct TreeNode* node = nodeQueue[left++];
if (isOrderLeft) {
levelList[rear++] = node->val;
} else {
levelList[--front] = node->val;
}
if (node->left) {
nodeQueue[right++] = node->left;
}
if (node->right) {
nodeQueue[right++] = node->right;
}
}
int* tmp = malloc(sizeof(int) * (rear - front));
for (int i = 0; i < rear - front; i++) {
tmp[i] = levelList[i + front];
}
ans[*returnSize] = tmp;
(*returnColumnSizes)[*returnSize] = rear - front;
(*returnSize)++;
isOrderLeft = !isOrderLeft;
}
return ans;
}
|
复杂度分析
,
,
,
,
,
,
,
,
,
,
,
>