一、剑指 Offer 32 - I. 从上到下打印二叉树

要求：从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

思路：使用队列进行操作。

  1. 添加节点a
  2. 节点a出队，打印value
  3. 如果节点a有左节点b和右节点c，将b和c添加到队列。
  4. 循环，直到队列为空。
  5. 特殊情况：当二叉树为空树，返回空数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int[] levelOrder(TreeNode root) {
    if(root == null){
        return new int[0];
    }
    Queue<TreeNode> nodeQueue = new LinkedList<>();
    ArrayList<Integer> printList = new ArrayList<>();
    nodeQueue.offer(root);
    while(nodeQueue.size()!=0){
        TreeNode father = nodeQueue.poll();
        printList.add(father.val);
        if(father.left!=null){
            nodeQueue.offer(father.left);
        }
        if(father.right!=null){
            nodeQueue.offer(father.right);
        }
    }
    int[] arr = new int[printList.size()];
    for(int i = 0; i < printList.size();i++){
        arr[i] = printList.get(i);
    }
    return arr;
}

二、剑指 Offer 32 - II. 从上到下打印二叉树 II

要求：从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

解法1：自用解法，利用辅助队列

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
public static List<List<Integer>> levelOrder(TreeNode root) {
    // 判断根节点为null时的情况
    if(root == null){
        return new ArrayList<>();
    }
    // 定义主队列与辅助队列
    Queue<TreeNode> nodeQueue = new LinkedList<>();
    Queue<TreeNode> subQueue = new LinkedList<>();
    // 定义每一层打印出来的总列表和子列表
    ArrayList<Integer> printList = new ArrayList<>();
    List<List<Integer>> finalList = new ArrayList<>();
    // 导入根节点
    nodeQueue.offer(root);
    // 每次辅助队列都会抛回给主队列节点，所以当辅助队列无节点可抛，主队列接收不到节点后，结束循环。
    while(nodeQueue.size()!=0) {
         // 主队列每次循环都是一整层的节点
         // 当主队列不为空时，把主队列里所有的节点导出，并打印。
         // 将主队列中所有的节点扔给辅助队列。
        while (nodeQueue.size() != 0) {
            TreeNode father = nodeQueue.poll();
            subQueue.offer(father);
            printList.add(father.val);
        }
        // 向总列表中添加每一层的子列表，添加后初始化子列表
        finalList.add(printList);
        printList = new ArrayList<>();
        // 当主队列抛出一整层的节点后，辅助队列接受了这一整层的节点。
        // 辅助队列开始生成这一层节点的下层所有的节点，并把这些下层节点抛回给主队列
        // 实现逐层打印
        while (subQueue.size() != 0) {
            TreeNode subFather = subQueue.poll();
            if (subFather.left != null) {
                nodeQueue.offer(subFather.left);
            }
            if (subFather.right != null) {
                nodeQueue.offer(subFather.right);
            }
        }
    }
    // 返回总列表
    return finalList;
}

解法2：标准答案

不用辅助队列，使用queue.size()方法当场打印。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<List<Integer>> levelOrder(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    List<List<Integer>> res = new ArrayList<>();
    if(root != null) queue.add(root);
    while(!queue.isEmpty()) {
        List<Integer> tmp = new ArrayList<>();
        //queue.size()在第一次循环时，返回的正是当且层的节点数
        for(int i = queue.size(); i > 0; i--) {
            TreeNode node = queue.poll();
            tmp.add(node.val);
            if(node.left != null) queue.add(node.left);
            if(node.right != null) queue.add(node.right);
        }
        res.add(tmp);
    }
    return res;
}

三、剑指 Offer 32 - III. 从上到下打印二叉树 III

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

解法1：使用栈进行反转

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
public static List<List<Integer>> levelOrder(TreeNode root) {
    // 判断根节点为null时的情况
    if (root == null) {
        return new ArrayList<>();
    }
    // 定义主队列与辅助队列
    Queue<TreeNode> nodeQueue = new LinkedList<>();
    Queue<TreeNode> subQueue = new LinkedList<>();
    // 定义每一层打印出来的总列表和子列表
    ArrayList<Integer> printList = new ArrayList<>();
    List<List<Integer>> finalList = new ArrayList<>();
    Stack<Integer> inverseList = new Stack<>();
    int count = 0;
    // 导入根节点
    nodeQueue.offer(root);
    // 每次辅助队列都会抛回给主队列节点，所以当辅助队列无节点可抛，主队列接收不到节点后，结束循环。
    while (nodeQueue.size() != 0) {
        // 主队列每次循环都是一整层的节点
        // 当主队列不为空时，把主队列里所有的节点导出，并打印。
        // 将主队列中所有的节点扔给辅助队列。
        while (nodeQueue.size() != 0) {
            TreeNode father = nodeQueue.poll();
            subQueue.offer(father);
            if (count % 2 == 0){
                printList.add(father.val);
            }else{
                inverseList.push(father.val);
            }

        }
        while(!inverseList.empty()){
            printList.add(inverseList.pop());
        }
        // 向总列表中添加每一层的子列表，添加后初始化子列表
        count++;
        finalList.add(printList);
        printList = new ArrayList<>();
        // 当主队列抛出一整层的节点后，辅助队列接受了这一整层的节点。
        // 辅助队列开始生成这一层节点的下层所有的节点，并把这些下层节点抛回给主队列
        // 实现逐层打印
        while (subQueue.size() != 0) {
            TreeNode subFather = subQueue.poll();
            if (subFather.left != null) {
                nodeQueue.offer(subFather.left);
            }
            if (subFather.right != null) {
                nodeQueue.offer(subFather.right);
            }
        }
    }
    // 返回总列表
    return finalList;
}

解法2：使用Collections.reverse()

在解法1的基础上，使用reverse方法直接反转子列表，省去了把列表元素压入栈的过程。

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
public static List<List<Integer>> levelOrder(TreeNode root) {
    // 判断根节点为null时的情况
    if (root == null) {
        return new ArrayList<>();
    }
    // 定义主队列与辅助队列
    Queue<TreeNode> nodeQueue = new LinkedList<>();
    Queue<TreeNode> subQueue = new LinkedList<>();
    // 定义每一层打印出来的总列表和子列表
    ArrayList<Integer> printList = new ArrayList<>();
    List<List<Integer>> finalList = new ArrayList<>();
    int count = 0;
    // 导入根节点
    nodeQueue.offer(root);
    // 每次辅助队列都会抛回给主队列节点，所以当辅助队列无节点可抛，主队列接收不到节点后，结束循环。
    while (nodeQueue.size() != 0) {
        // 主队列每次循环都是一整层的节点
        // 当主队列不为空时，把主队列里所有的节点导出，并打印。
        // 将主队列中所有的节点扔给辅助队列。
        while (nodeQueue.size() != 0) {
            TreeNode father = nodeQueue.poll();
            subQueue.offer(father);
            printList.add(father.val);
        }
        if(count % 2 ==0){
            finalList.add(printList);
        }else {
            Collections.reverse(printList);
            finalList.add(printList);
        }

        // 向总列表中添加每一层的子列表，添加后初始化子列表
        count++;
        printList = new ArrayList<>();
        // 当主队列抛出一整层的节点后，辅助队列接受了这一整层的节点。
        // 辅助队列开始生成这一层节点的下层所有的节点，并把这些下层节点抛回给主队列
        // 实现逐层打印
        while (subQueue.size() != 0) {
            TreeNode subFather = subQueue.poll();
            if (subFather.left != null) {
                nodeQueue.offer(subFather.left);
            }
            if (subFather.right != null) {
                nodeQueue.offer(subFather.right);
            }
        }
    }
    // 返回总列表
    return finalList;
}

解法3: 类似于第二题的标准答案，直接利用内层循环反向打印

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
public static List<List<Integer>> levelOrder(TreeNode root) {
    Queue<TreeNode> nodeQueue = new LinkedList<>();
    ArrayList<Integer> printList = new ArrayList<>();
    List<List<Integer>> finalList = new ArrayList<>();
    int count = 0;
    nodeQueue.offer(root);
    while (nodeQueue.size() != 0) {
        for (int i = nodeQueue.size(); i > 0 ;i--) {
            TreeNode father = nodeQueue.poll();
            if(father==null){
                return new ArrayList<>();
            }
            if(father.left!=null){
                nodeQueue.offer(father.left);
            }
            if (father.right!=null){
                nodeQueue.offer(father.right);
            }
            printList.add(father.val);
        }
        if (count % 2 != 0) {
            Collections.reverse(printList);
        }
        finalList.add(printList);
        count++;
        printList = new ArrayList<>();
    }
    return finalList;
}