题目描述

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

题目分析

使用队列进行遍历，核心是借助队列的大小得到这一层节点的数量，根据数量实现统一出队以及下一层的统一入队。

Java

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    if (root == null) {
        return ans;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> list = new ArrayList<>();
        while (size > 0) {
            TreeNode node = queue.poll();
            list.add(node.val);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            size--;
        }
        if (!list.isEmpty()) {
            ans.add(list);
        }
    }
    return ans;
}

Kotlin

fun levelOrder(root: TreeNode?): List<List<Int>> {
    val ans = ArrayList<List<Int>>()
    if (root == null) {
        return ans
    }
    val queue = LinkedList<TreeNode>()
    queue.offer(root)
    while (!queue.isEmpty()) {
        var size = queue.size
        val list = ArrayList<Int>()
        while (size > 0) {
            val node = queue.poll()
            list.add(node.`val`)
            if (node.left != null) {
                queue.offer(node.left)
            }
            if (node.right != null) {
                queue.offer(node.right)
            }
            size--
        }
        if (!list.isEmpty()) {
            ans.add(list)
        }
    }
    return ans
}