陈鹏的博客

每天进步一点点😉

0%

leetcode-103

发表于 更新于

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

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

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

1
2
3
4
5
3
  / \
 9  20
   /  \
  15   7

返回锯齿形层序遍历如下：

1
2
3
4
5
[
  [3],
  [20,9],
  [15,7]
]

广度优先遍历

利用双端队列和标识位维护当前层输入的顺序

如果是偶数层：从左向右添加，即节点从队尾添加

如果是奇数层：从右向左添加，即节点从对头添加

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
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;
        // 树的广度优先遍历一般是使用队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // 标识位，如果为true则表明是从左向右，如果为false则表明是从右向左
        boolean isLeft = true;
        while (!queue.isEmpty()) {
            // 层序遍历一般解法：首先获得该层的节点个数
            int size = queue.size();
            // 使用双端队列，维护顺序
            Deque<Integer> list = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                // 如果是要从左向右读，那么添加到队尾
                if (isLeft) {
                    list.addLast(node.val);
                } else { //弱国是要从右向左读，那么添加到对头
                    list.addFirst(node.val);
                }
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            // 每次遍历完一层，则更改标识符，表明下次的顺序与本次相反
            isLeft = !isLeft;
            ans.add(new LinkedList<>(list));
        }
        return ans;
    }

复杂度分析

时间复杂度：O(N)，其中 N 为二叉树的节点数。每个节点会且仅会被遍历一次。

空间复杂度：O(N)。需要维护存储节点的队列和存储节点值的双端队列，空间复杂度为 O(N)。

深度优先遍历

在递归调用过程中判断该层是要从左往右遍历还是从右向左遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public List<List<Integer>> zigzagLevelOrderDFS(TreeNode root) {
    List<Deque<Integer>> res = new ArrayList<>();
    dfs(root, 0, true, res);
    List<List<Integer>> ans = new ArrayList<>();
    for (Deque<Integer> re : res) {
        ans.add(new LinkedList<>(re));
    }
    return ans;
}

private void dfs(TreeNode root, int i, boolean isLeft, List<Deque<Integer>> ans) {
    if (root == null) return;
    if (ans.size() == i) {
        ans.add(new LinkedList<>());
    }
    if (isLeft) {
        ans.get(i).addLast(root.val);
    } else {
        ans.get(i).addFirst(root.val);
    }
    dfs(root.left, i + 1, !isLeft, ans);
    dfs(root.right, i + 1, !isLeft, ans);
}

复杂度分析

时间复杂度：O(N)，其中 N 为二叉树的节点数。每个节点会且仅会被遍历一次。

空间复杂度：O(N)。