一【题目类别】

• 二叉树

二【题目难度】

• 中等

三【题目编号】

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

四【题目描述】

• 给你二叉树的根节点 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

七【解题思路】

• 层序遍历肯定使用的是BFS（广度优先搜索）
• 基于这个思路进行层序遍历，对于层序遍历比较简单，直接扫描这一层的元素在队列弹出然后加入到结果数组中即可
• 但是题目要求存储的左右顺序不停的反转，所以设置一个标志位，一开始从左到右存储，然后每存储完一层之后，修改标志位，让其从右到左存储。通过不停的修改标志位来达到左右顺序不同的层序存储

八【时间频度】

• 时间复杂度：$O(n)$，其中$n$为树的节点个数
• 空间复杂度：$O(n)$，其中$n$为树的节点个数

九【代码实现】

1. Java语言版

package Tree;

import java.util.*;

public class p103_ZigzagOrderTraversalOfBinaryTrees {

    int val;
    p103_ZigzagOrderTraversalOfBinaryTrees left;
    p103_ZigzagOrderTraversalOfBinaryTrees right;

    public p103_ZigzagOrderTraversalOfBinaryTrees() {
    }

    public p103_ZigzagOrderTraversalOfBinaryTrees(int val) {
        this.val = val;
    }

    public p103_ZigzagOrderTraversalOfBinaryTrees(int val, p103_ZigzagOrderTraversalOfBinaryTrees left, p103_ZigzagOrderTraversalOfBinaryTrees right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public static void main(String[] args) {
        p103_ZigzagOrderTraversalOfBinaryTrees root = new p103_ZigzagOrderTraversalOfBinaryTrees(3);
        p103_ZigzagOrderTraversalOfBinaryTrees left = new p103_ZigzagOrderTraversalOfBinaryTrees(9);
        p103_ZigzagOrderTraversalOfBinaryTrees right = new p103_ZigzagOrderTraversalOfBinaryTrees(20);
        p103_ZigzagOrderTraversalOfBinaryTrees right1 = new p103_ZigzagOrderTraversalOfBinaryTrees(15);
        p103_ZigzagOrderTraversalOfBinaryTrees right2 = new p103_ZigzagOrderTraversalOfBinaryTrees(7);
        root.left = left;
        root.right = right;
        right.left = right1;
        right.right = right2;
        List<List<Integer>> res = zigzagLevelOrder(root);
        System.out.println("res = " + res);
    }

    public static List<List<Integer>> zigzagLevelOrder(p103_ZigzagOrderTraversalOfBinaryTrees root) {
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        boolean flag = true;
        if (root == null) {
            return res;
        }
        Queue<p103_ZigzagOrderTraversalOfBinaryTrees> queue = new ArrayDeque<p103_ZigzagOrderTraversalOfBinaryTrees>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            Deque<Integer> list = new LinkedList<Integer>();
            for (int i = 0; i < size; i++) {
                p103_ZigzagOrderTraversalOfBinaryTrees temp = queue.poll();
                if (flag) {
                    list.offerLast(temp.val);
                } else {
                    list.offerFirst(temp.val);
                }
                if (temp.left != null) {
                    queue.offer(temp.left);
                }
                if (temp.right != null) {
                    queue.offer(temp.right);
                }
            }
            res.add(new LinkedList<Integer>(list));
            if (flag) {
                flag = false;
            } else {
                flag = true;
            }
        }
        return res;
    }

}
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

2. C语言版

#include
#include
#include

struct TreeNode
{
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
};

int** zigzagLevelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes)
{
	int** res = (int**)malloc(sizeof(int*) * 2001);
	*returnColumnSizes = (int*)malloc(sizeof(int) * 2001);
	*returnSize = 0;
	struct TreeNode* queue[2001];
	int front = 0;
	int rear = 0;
	bool flag = true;
	if (root == NULL)
	{
		(*returnColumnSizes)[*returnSize] = 0;
		return res;
	}
	queue[rear++] = root;
	while (front != rear)
	{
		res[*returnSize] = (int*)malloc(sizeof(int) * 2001);
		(*returnColumnSizes)[*returnSize] = 0;
		int size = (rear - front + 2001) % 2001;
		int count = 0;
		for (int i = 0; i < size; i++)
		{
			struct TreeNode* temp = queue[front++];
			if (flag)
			{
				res[*returnSize][count] = temp->val;
			}
			else
			{
				res[*returnSize][size - count - 1] = temp->val;
			}
			if (temp->left != NULL)
			{
				queue[rear++] = temp->left;
			}
			if (temp->right != NULL)
			{
				queue[rear++] = temp->right;
			}
			count++;
		}
		(*returnColumnSizes)[*returnSize] = count;
		*returnSize = *returnSize + 1;
		if (flag)
		{
			flag = false;
		}
		else
		{
			flag = true;
		}
	}
	return res;
}

/*主函数省略*/
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

十【提交结果】

1. Java语言版
   

2. C语言版