102. Binary Tree Level Order Traversal

题目：

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,#,#,15,7},

return its level order traversal as:

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

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

链接： http://leetcode.com/problems/binary-tree-level-order-traversal/

题解：用两个list来储存上一层和当前层。应该还可以减少空间复杂度。第二遍要试一下DFS

class Solution(object):
    def levelOrder(self, root):
        if not root:
            return []
        prev = [root]
        cur = []
        result = [[root.val]]
        while prev:
            for elem in prev:
                if elem.left:
                    cur.append(elem.left)
                if elem.right:
                    cur.append(elem.right)
            if cur:
                result.append([c.val for c in cur])
            prev, cur = cur, []
        return result

5/13/2017

2ms, 45%

Queue的offer/add的区别，在于add有capacity的限制

poll/remove也是一对

 1 public class Solution {
 2     public List<List<Integer>> levelOrder(TreeNode root) {
 3         List<List<Integer>> ret = new ArrayList<>();
 4         if (root == null) return ret;
 5         
 6         Queue<TreeNode> queue = new LinkedList<TreeNode>();
 7         queue.offer(root);
 8         
 9         while (!queue.isEmpty()) {
10             int size = queue.size();
11             List<Integer> list = new ArrayList<Integer>();
12             for (int i = 0; i < size; i++) {
13                 TreeNode node = queue.poll();
14                 list.add(node.val);
15                 if (node.left != null) {
16                     queue.offer(node.left);
17                 }
18                 if (node.right != null) {
19                     queue.offer(node.right);
20                 }
21             }
22             ret.add(list);
23         }
24         return ret;
25     }
26 }