Leetcode102. 二叉树的层序遍历

题目描述

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

思路分析

1. 二叉树的层序遍历，及一层一层的遍历二叉树，将每一层的节点值记录在集合中,再将每一层的结果记录到容器并返回
2. 由题意，使用广度优先的思想
3. 对每一层的所有节点维护一个队列和一个保存节点值的集合，每次遍历该层所对应队列中的节点，将其值保存到该层所对应的集合中，并判断当前节点是否含有子节点，如果有，则再将其放入到下一层节点所对应的队列中，依次类推
4. 最后当队列为空时，说明所有层的所有节点全部遍历完毕
5. 详细思路见下

源码及分析

  /**
     *
     * @param root 根节点
     * @return 返回按层序遍历的节点值
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        //创建集合保存结果
        List<List<Integer>> res = new ArrayList<>();
        //数据校验
        if (root == null){
            return res;
        }
        //维护一个队列保存当前层的节点对象
        Queue<TreeNode> queue = new LinkedList<>();
        //先将根节点放入队列
        queue.offer(root);
        //使用广度优先思想遍历每一层的节点
        while (!queue.isEmpty()){
            //创建集合保存每一层的节点值
            ArrayList<Integer> list = new ArrayList<>();
            //记录每一层的节点个数，用于遍历
            int currentSize = queue.size();
            //层层遍历
            for (int i = 0; i < currentSize; i++) {
                //去除队列中的节点
                TreeNode node = queue.poll();
                //将其值记录到集合中
                list.add(node.val);
                //判断当前节点有没有子节点，如果有则入队列作为下一层遍历其值
                if (node.left != null){
                    queue.offer(node.left);
                }
                if (node.right != null){
                    queue.offer(node.right);
                }
            }
            //记录结果
            res.add(list);
        }
        return res;
    }

节点类

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

Leetcode102. 二叉树的层序遍历