[剑指Offer] Day 06

题目来源：剑指 Offer 32 - I. 从上到下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

解题思路：广度优先遍历二叉树。若根节点非空，则将其压入队列。当队列非空时，从队列中取出一个节点，将值加入可变列表。依次将其左右子树（非空）压入队列。从可变列表中取出值，依次放入数组，返回结果数组。

时间复杂度：O(N)

空间复杂度：O(N)

class Solution {
    fun levelOrder(root: TreeNode?): IntArray {
        if (root == null) return intArrayOf()
        val queue = LinkedList<TreeNode>()
        val arr = mutableListOf<Int>()
        queue.offer(root)
        while (queue.isNotEmpty()) {
            val node = queue.poll()
            arr.add(node.`val`)
            node.left?.let {
                queue.offer(node.left)
            }
            node.right?.let {
                queue.offer(node.right)
            }
        }

        val res = IntArray(arr.size)
        arr.forEachIndexed { index, i ->
            res[index] = i
        }
        return res

    }
}

题目来源：剑指 Offer 32 - II. 从上到下打印二叉树 II

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

解题思路：与上一题思路类似，这题复杂之处在于需要将二叉树分层输入到不同的字数组中。借鉴@Krahets的思路，使用队列的size来判断当前层遍历是否结束。

时间复杂度：O(N)

空间复杂度：O(N)

class Solution {
    fun levelOrder(root: TreeNode?): List<List<Int>> {
        val queue = LinkedList<TreeNode>()
        val res = ArrayList<ArrayList<Int>>()
        if (root != null) queue.offer(root) 
        while (queue.isNotEmpty()) {
            val tmp = ArrayList<Int>()
            for (i in 0 until queue.size) {
                val node = queue.poll()
                tmp.add(node.`val`)
                node.left?.let {
                    queue.offer(it)
                }
                node.right?.let {
                    queue.offer(it)
                }
            }
            res.add(tmp)
        }
        return res   

    }
}