LeetCode 102. 二叉树的层序遍历

102. 二叉树的层序遍历

解题思路

层序遍历二叉树，使用队列来实现。首先将根节点加入队列，然后不断从队列中取出节点，并将其左右子节点加入队列，直到队列为空为止。在这个过程中，我们可以记录每一层的节点值，最终返回一个包含每一层节点值的列表。

参考代码

	ArrayDeque	LinkedList
底层结构	循环数组	双向链表
内存布局	连续内存，缓存友好	节点分散在堆上
null 元素	不允许	允许
额外开销	扩容时数组复制	每个节点多两个指针

---

class Solution {

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        ArrayDeque<TreeNode> queue = new ArrayDeque<>(); // 推荐
        // Queue<TreeNode> queue = new LinkedList<>(); // 执行耗时更短一些？

        if (root == null) {
            return ans;
        }

        queue.offer(root);
        while(queue.size() != 0) {
            int size = queue.size();
            List<Integer> row = new ArrayList<>();
            for(int i = 0; i < size; i ++) {
                TreeNode node = queue.poll();
                row.add(node.val);
                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
            }
            ans.add(row);
        }
        return ans;
    }
}