题目

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

例如:
给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

解题方法

题目要求返回一个嵌套链表List>，按层次输出，则需要将不同层次的节点保存在不同的子链表中，那么使用队列来进行层次遍历时，需要用两个队列，当前队列cur和一个下一层的队列sub，访问当前队列时，将各节点的子节点入列到下一层队列中，在当前层遍历结束后，交换cur和sub，下一次循环遍历下一层节点。

// Method_01  2ms  84.73%
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) {  //边界判断
        return result;
    }

    Deque<TreeNode> cur = new LinkedList<>();  //队列保存一层        
    Deque<TreeNode> sub = new LinkedList<>();  //队列保存下一层
    Deque<TreeNode> exc;

    TreeNode node;
    cur.addLast(root);  //先保存根节点

    while(!cur.isEmpty()) {
        List<Integer> layout = new ArrayList<>();  //保存一层的节点
        while(!cur.isEmpty()) {
            node = cur.removeFirst();   //弹出前面第一个节点
            layout.add(node.val);       //添加到输出集合中
             
            if (node.left != null) {    //把弹出的节点的左节点加入下一层队列
                sub.addLast(node.left);
            }
                
            if (node.right != null) {   //把弹出的节点的右节点加入下一层队列
                sub.addLast(node.right);
            }
        }

        exc = cur;       //交换
        cur = sub;            
        sub = exc;

        result.add(layout);  //添加到结果集里
    }
    return result;
}