了解今天的题目前，可以去我的博客看看二叉树和BFS（宽度优先遍历）知识：二叉树 | IT蛋的个人博客 (xcscx.github.io)

从上到下打印二叉树

medium 原题连接：从上到下打印二叉树

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

示例：

给定二叉树: [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
返回 [3,9,20,15,7]

限制：

  1. 节点总数 <= 1000

解题思路

二叉树的广度优先算法，因为输出时不需要考虑节点之间的关系，所以按照从上至下，从左至右的顺序存储输出即可

二叉树的BFS（宽度优先遍历）最常见的实现方式是利用队列进行存储，因为队列是先进先出，所以在遍历每一节点时将全部子节点填入队列，这样，在子节点全部遍历完成前，子节点的子节点不会被遍历到，依次类推，直到队列为空

Java代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
        
        ArrayList<Integer> utilsArray = new ArrayList<>();
        Queue<TreeNode> treeQueue = new LinkedList<TreeNode>();
        treeQueue.add(root);
        while(null != treeQueue.element()) {
            TreeNode mid = treeQueue.element();
            if(mid.left != null) {
                treeQueue.add(mid.left);
            }
            if(mid.right != null) {
                treeQueue.add(mid.right);
            }
            utilsArray.add(treeQueue.poll().val);
        }
        int[] ans = new int[utilsArray.size()];
        for(int i=0; i<utilsArray.size(); i++){
            ans[i] = utilsArray.get(i);
        }
        return ans;
    }
}

从上到下打印二叉树 II

Easy 原题连接：从上到下打印二叉树 II

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

示例：

给定二叉树: [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：     
[
  [3],
  [9,20],
  [15,7]
]

提示：

  1. 节点总数 <= 1000

解题思路

同样是宽度优先遍历，但是要求记录每一层节点的长度，或者说记录每一层节点的最后一个节点是谁

本来实现是通过新增两个TreeNode节点，一个记录当前层最后一个节点，一个记录下一层最后一个节点

后者在每一个子节点添加时做更新，当节点来到当前层的最后节点，输出数组并更新当前最后节点为下一层最后节点值

不过实现确实过于冗长了…

这里展示另一位大佬的思路：因为每次遍历完一层，队列中就只剩下下一层的全部节点，我们可以借由此作为下一层读取节点的个数，以此类推

Java代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        Queue<TreeNode> treeQueue = new LinkedList<>();

        if(root != null) treeQueue.add(root);
        
        while(!treeQueue.isEmpty()) {
            List<Integer> mid = new ArrayList<>();
            for(int i=treeQueue.size(); i>0; i--) {
                TreeNode midNode = treeQueue.peek();
                if(midNode.left != null) treeQueue.add(midNode.left);
                if(midNode.right != null) treeQueue.add(midNode.right);
                mid.add(treeQueue.poll().val);
            }
            ans.add(mid);
        }
        return ans;
    }
}

从上到下打印二叉树 III

medium 原题连接：从上到下打印二叉树 III

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

示例：

给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：

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

限制：

  • 节点总数 <= 1000

解题思路

思路和上一题差不多，同样是分层输出的宽度优先，不过有一个输出顺序需要考虑

这里首先考虑到每层遍历时的输入，说白了就是一个正序一个倒序，只要在每一层输入时一个正着输入一个倒着输入就好

适用每层遍历后，结果的长度判断什么时候正序什么时候倒序

将原本用于存储的List 转为 LinkedList 适用头插尾插方法实现

Java代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        Queue<TreeNode> treeQueue = new LinkedList<>();

        if(root != null) treeQueue.add(root);
        while(!treeQueue.isEmpty()) {
            LinkedList<Integer> mid = new LinkedList<>();
            for(int i=treeQueue.size(); i>0; i--) {
                TreeNode midNode = treeQueue.peek();
                if(midNode.left != null) treeQueue.add(midNode.left);
                if(midNode.right != null) treeQueue.add(midNode.right);
                if(ans.size()%2 == 0) mid.addLast(treeQueue.poll().val);
                else mid.addFirst(treeQueue.poll().val);
            }
            ans.add(mid);
        }
        return ans;
    }
}