LeetCode-102. 二叉树的层序遍历

题目描述

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

链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

实现

    /**
     * 层序遍历
     */
    public static List<List<String>> levelOrder(TreeNode<String> root) {
        //存储各个节点的内容
        List<List<String>> levelNodeDataList = new LinkedList<>();

        if (root != null) {
            //把"当前层节点"和"下一层节点"全部存到一个"队列"中,当前层的节点添加到队列的前边,下一层节点添加到队列的尾部
            //遍历队列的时候,需要知道"当前层和下一层的"分界点,需要在遍历前保存一个"当前队列"的容量(此时还没添加下一层节点,所以仅仅包含当前层节点的个数)
            //用"队列的链式存储结构(不用顺序结构)"节省内存(顺序存储结构的话(ArrayList)内部使用动态数组的方式实现,会有一部分无用内存的浪费)
            Queue<TreeNode<String>> curLevelNodeList = new LinkedList<>();
            curLevelNodeList.add(root);

            while (!curLevelNodeList.isEmpty()) {
                //记录下当前层有多少个节点
                int curNodeSize = curLevelNodeList.size();
                //存储当前层的节点数据
                LinkedList<String> curLevelNodeDataList = new LinkedList<>();

                for (int i = 0; i < curNodeSize; i++) {
                    TreeNode<String> node = curLevelNodeList.poll();

                    if (node != null) {
                        //
                        curLevelNodeDataList.add(node.data);

                        //
                        if (node.left != null) {
                            curLevelNodeList.add(node.left);
                        }
                        //
                        if (node.right != null) {
                            curLevelNodeList.add(node.right);
                        }
                    }
                }

                levelNodeDataList.add(curLevelNodeDataList);
            }
        }

        return levelNodeDataList;
    }