102.二叉树的层序遍历Java

题目描述

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

输入输出样式

示例1：
tn = [3,9,20,null,null,15,7]

输出：[[3], [9, 20], [15, 7]]

本题来自LeetCode：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

思路

利用队列完成对二叉树的层次遍历， 初始化将根节点入队，在当前的队列非空则进行出队，同时将出队的节点的左右子树(如果存在)加入到队列。如此反复

算法分析

时间复杂度O(n），空间复杂度为O(n)

求解函数

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new LinkedList<List<Integer>>();
        if (root == null) return list;
        Queue<TreeNode> que = new LinkedList();
        //根节点入队
        que.offer(root);
        while (!que.isEmpty()) {
            List<Integer> temp = new LinkedList<>();
            int size = que.size();
            //当前扫描的层的所有节点进行出队操作
            while (size > 0) {
                TreeNode tn = que.poll();
                temp.add(tn.val);
                if (tn.left != null) {
                    que.offer(tn.left);
                }
                if (tn.right != null) {
                    que.offer(tn.right);
                }
                --size;
            }
            list.add(temp);
        }
        return list;
    }