Binary Tree Level Order Traversa

• 描述
  Given a binary tree, return the level order traversal of its nodes’ values.

For example: Given binary tree {3,9,20,#,#,15,7}, return
[
[3],
[9,20],
[15,7]
]

• 分析
  不需要保存具体层的很简单，参考广度优先搜索BFS思想，只需要一个辅助队列，本题需要两个辅助队列，一个保存0层的节点，一个保存1层的节点（也就是0层的下层节点），当0层节点的队列出队完毕，那么1层队列也填满，交换两个队列，扫描1层的下层节点，也就是2层，如此循环下去，直到最下层叶子扫描完毕。

• 时间复杂度O(n)，空间复杂度O(n)

import java.util.*;

public class Solution {
    public List<List<Integer>> levelOrderTraverse(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null)
            return result;
        Queue<TreeNode> rootQueue = new LinkedList<>();
        Queue<TreeNode> leafQueue = new LinkedList<>();
        rootQueue.add(root);
        while(!rootQueue.isEmpty()) {
            List<Integer> levelRes = new ArrayList<>();
            while(!rootQueue.isEmpty()) {
                TreeNode p = rootQueue.poll();
                levelRes.add(p.val);
                if(p.left != null) leafQueue.add(p.left);
                if(p.right != null) leafQueue.add(p.right);
            }
            result.add(levelRes);
            // 交换上层和下层的队列
            Queue<TreeNode> tmp = rootQueue;
            rootQueue = leafQueue;
            leafQueue = tmp;
        }
        return result;
    }
}