长大后想做什么？做回小孩！

0%

LeetCode——二叉树的锯齿形层次遍历

发表于 更新于 分类于 Valine：
本文字数： 135

NO.103 二叉树的锯齿形层次遍历 中等

Gjau7R.png

思路一：层序遍历 题上说了就是层序遍历，需要进行一点改进使其Z字形层序遍历。

偶数层从左向右遍历(尾插法记录元素)，奇数层从右向左遍历(头插法)。

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>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> queue = new LinkedList<>();
    //记录当前层数
    int depth = 0;
    queue.add(root);
    while (!queue.isEmpty()) {
        List<Integer> list = new LinkedList<>();
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode poll = queue.poll();
            //偶数层尾插法，奇数层头插法
            if (depth % 2 == 0) list.add(poll.val);
            else list.add(0, poll.val);
            if (poll.left != null) queue.add(poll.left);
            if (poll.right != null) queue.add(poll.right);
        }
        res.add(list);
        depth++;
    }
    return res;
}

时间复杂度：O(n) 遍历一次

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github