LeetCode 102 Binary Tree Level O

LeetCode 102 Binary Tree Level Order Traversal

===================

二叉树层序遍历，要求将每一层的元素作为一个列表，最后将每层的列表组成大列表作为返回值。层序遍历可以使用dfs标记深度，或使用queue直接bfs。

代码中的细节:

java中二位数组如何定义？
注意实例化时需使用ArrayList。

List<List<Integer>> res = new ArrayList<List<Integer>>(); 

层序遍历如何实现将同一行的元素放入同一列表中？
这里需要用变量mark来维护每一层元素的个数，具体地，每层开始时队列的大小就是该层元素个数。

while (!q.isEmpty()) 
{  int mark = q.size(); 
  // 若mark个元素均出队，则认为该层遍历完毕。 
  for (int i = 0; i < mark; i++) { 
  ... 
  }
}

java中队列Queue的基本操作？
队列Queue在定义时一般由LinkedList实现。入队和出队操作建议使用offer()和poll()方法，因为这两个方法会返回操作成功与否，若不成功返回false，而不是抛出异常。

具体代码如下：

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        
        if (root == null) return res;
        
        q.offer(root);
        int mark = 0;
        while (!q.isEmpty()) {
            mark = q.size();
            List<Integer> tmpList = new ArrayList<Integer>();
            TreeNode tmpNode = new TreeNode(0);
            for (int i = 0; i < mark; i++) {
                tmpNode = q.poll();
                tmpList.add(tmpNode.val);
                if (tmpNode.left != null) q.offer(tmpNode.left);
                if (tmpNode.right != null) q.offer(tmpNode.right);
            }
            res.add(tmpList);
        }
        return res;
    }
}