前言

层次遍历是操作树的基础，而分层遍历就是层次遍历的变体，一般可用队列+层size来分层，也可以递归遍历+level来分层。通过锯齿形分层遍历二叉树来练习前序遍历+level来分层。

一、二叉树的锯齿形层序遍历

二、递归遍历+level分层

package everyday.medium;

import java.util.ArrayList;
import java.util.List;

// 二叉树的锯齿形层序遍历
public class ZigzagLevelOrder {
    /*
    target：单数双数层倒着输出，双数层正着输出，从0层开始。
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        // 前序遍历 + level 实现层次遍历。
        List<List<Integer>> ans = new ArrayList<>();
        preOrder(root, ans, 0);
        return ans;
    }

    private void preOrder(TreeNode root, List<List<Integer>> ans, int level) {
        // null节点，递归终止。
        if (root == null) return;
        // 单数层倒着输出，双数层正着输出，从0层开始。
        // 一层一层往下走的，所以选择取等。
        if (level == ans.size()) ans.add(new ArrayList<>());
        List<Integer> cur = ans.get(level);
        if ((level & 1) == 0) cur.add(root.val);
        else cur.add(0, root.val);
        // 前序遍历
        preOrder(root.left, ans, level + 1);
        preOrder(root.right, ans, level + 1);
    }

    // Definition for a binary tree node.
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

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

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

总结

1）层次遍历，分层遍历。
2）队列+层size分层 | 递归遍历 + level分层。

参考文献

[1] LeetCode 二叉树的锯齿形层序遍历