LeetCode_15_BinaryTreeLevelOrderTraversal

1. question: 二叉树的层序遍历（中等）

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

2. answers

思路：

层序遍历比较简单，直接用队列存储节点，将节点的左右孩子节点按顺序存入队列即可。然后再取出即可。

关键的一个问题是，如何将一层的节点封装成一个List。即怎么判断从队列中取出的节点是否属于当前层。

一种思路是：在遍历的时候，记录其下一层孩子节点的数量。当从队列中取元素的时候，判断已取出的数量是否达到了该层的数量，如果达到了，则将已有的List加入到结果中，并新建空的List。

代码如下所示：

public class Solution_0013 {

    public static List<List<Integer>> levelOrder(TreeNode root) {

        // 存储结果
        List<List<Integer>> result = new ArrayList<>();
        
        // 保存result中的子List
        List<Integer> subResult = new ArrayList<>();

        if(root == null) {
            return result;
        }

        // 队列，用于存储遍历的节点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        // 保存每一层的节点数量
        Queue<Integer> nodeChilds = new LinkedList<>();

        // 首先将1加入到nodeChilds中，相当于只有一个根节点
        nodeChilds.offer(1);

        // 保存一层的节点个数
        int offerLength = 0;

        // 保存多少个节点值存入一个List中。
        int pollLength = nodeChilds.poll();

        while(!queue.isEmpty()) {

            // 如果是0，说明上一个层的孩子节点已经遍历完，此时需要将形成的该子List加入到result中，并生成新的List。
            // 注意，如果是最后一个子List，那么因为已经队列为空，所以不会进入循环，所以需要在循环结束后将子List加入result中。
            if(pollLength == 0) {
                result.add(subResult);
                subResult = new ArrayList<>();

                // 获取下一个层的子节点数
                pollLength = nodeChilds.poll();
            }

            root = queue.poll();

            // 将子节点加入，并数量自减1
            subResult.add(root.val);
            pollLength -= 1;

            if(root.left != null) {
                queue.offer(root.left);
                offerLength += 1;
            }

            if(root.right != null) {
                queue.offer(root.right);
                offerLength += 1;
            }

            // 注意，只有这一层节点的孩子节点数量不是0时，也就是有孩子时，才将孩子数量加入，并将offerLength清零
            // 什么时候加入呢？即只有这一层结束，说明所有可能的孩子节点都已经计数完毕了。
            // 怎么判断这一层是否有没有结束呢？即 pollLength 为 0 时，说明
            if(offerLength != 0 && pollLength == 0) {

                nodeChilds.offer(offerLength);
                offerLength = 0;
            }
        }

        // 将最后一个子List加入到result中
        result.add(subResult);

        return result;
    }

    public static void main(String[] args) {

        TreeNode tn1 = new TreeNode(7);
        TreeNode tn2 = new TreeNode(15);
        TreeNode tn3 = new TreeNode(20, tn2, tn1);

        TreeNode tn4 = new TreeNode(9);

        TreeNode root = new TreeNode(3, tn4, tn3);

        List<List<Integer>> result = levelOrder(root);
        for(List<Integer> i: result) {
            for(Integer j : i) {
                System.out.print(j + "  ");
            }
            System.out.println();
        }
    }
}

思路2：

上面的思路其实没问题，但是实现过程变复杂了。保存下一层要遍历的节点数量，只需要用一个变量代替即可，不需要用队列。而且下一层要遍历的节点数量，实际上就是循环开始时队列的长度。

代码如下所示：

public class Solution_0013_03 {

    public static List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> result = new ArrayList<>();

        if(root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);

        int length = 1;

        while(!queue.isEmpty()) {

            // 每次循环代表循环一层，所以获取即将要循环层的节点个数
            length = queue.size();
            List<Integer> subResult = new ArrayList<>();

            while(length > 0) {

                root = queue.poll();

                subResult.add(root.val);

                // 将下一层要循环的节点加入到队列中
                if(root.left != null) {
                    queue.offer(root.left);
                }

                if(root.right != null) {
                    queue.offer(root.right);
                }

                length --;
            }

            result.add(subResult);
        }

        return  result;
    }

    public static void main(String[] args) {
        TreeNode tn1 = new TreeNode(7);
        TreeNode tn2 = new TreeNode(15);
        TreeNode tn3 = new TreeNode(20, tn2, tn1);

        TreeNode tn4 = new TreeNode(9);

        TreeNode root = new TreeNode(3, tn4, tn3);

        List<List<Integer>> result = levelOrder(root);
        for(List<Integer> i: result) {
            for(Integer j : i) {
                System.out.print(j + "  ");
            }
            System.out.println();
        }
    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。