103. 二叉树的锯齿层次遍历

发表于 | 阅读次数:
字数统计: 350 | 阅读时长 ≈ 1

二叉树的锯齿层次遍历

LeetCode 103

英文版

中文版

或者叫 剑指offer第三题 之字形打印二叉树

题目

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

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

3

/ \
9 20
/ \
15 7
返回锯齿形层次遍历如下：

[
[3],
[20,9],
[15,7]
]

注意

  1. List<List> list = new ArrayList<List>();的声明方式；
  2. levelList在第二个for循环之前要清空；
  3. 最后一次的list.add(levelList) 要进行判空。

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * @description:
 * @author: rhsphere
 * @since: 2019-11-05 15:51 by jdk 1.8
 */
public class ZigzagLevelOrder {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();

        if (root == null)
            return list;
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();

        TreeNode node;
        stack1.push(root);

        while (!stack1.empty() || !stack2.empty()) {
            List<Integer> levelList = new ArrayList<>();
            while (!stack1.empty()) {
                node = stack1.pop();
                levelList.add(node.val);
                if (node.left != null)
                    stack2.push(node.left);
                if (node.right != null)
                    stack2.push(node.right);
            }
            list.add(levelList);

            levelList = new ArrayList<>();
            while (!stack2.empty()) {
                node = stack2.pop();
                levelList.add(node.val);
                if (node.right != null)
                    stack1.push(node.right);
                if (node.left != null)
                    stack1.push(node.left);
            }
            if (!levelList.isEmpty())
                list.add(levelList);
        }
        return list;
    }
}
0%