84. 二叉树的层序遍历

题目

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

示例 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

思路

class Solution {
    fun levelOrder(root: TreeNode?): List<List<Int>> {
        val result = mutableListOf<MutableList<Int>>()
        if (root == null) {
            return result
        }
        val queue = ArrayDeque<TreeNode?>()

        queue.addLast(root)

        while (queue.isNotEmpty()) {
            val size = queue.size
            val list = mutableListOf<Int>()
            for (i in 0 until size) {
                val node = queue.removeFirst()
                node?.let {
                    list.add(it.`val`)
                    if (it.left != null) {
                        queue.addLast(it.left)
                    }
                    if (it.right != null) {
                        queue.addLast(it.right)
                    }
                }
            }
            result.add(list)
        }
        return result
    }
}

复杂度

• 时间复杂度: O(n)
• 空间复杂度: O(w) w是层的宽度

• 下一题

• 邮箱 ：charon.chui@gmail.com
• Good Luck!