Binary Tree Level Order Traversal java实现

浏览数：16 / 时间：2015年06月08日

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

    3
   /   9  20
    /     15   7

return its level order traversal as:

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

实现的关键在于定义两个标记位和队列：
1、标志位last和end。last为记录的是本层次的最后一个最后一个结点，end用于寻找下一层的最后一个结点。
2、队列是用于存储每个结点。

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> list = new ArrayList<>();
            List<Integer> lst = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            TreeNode last =root;
            TreeNode end = null;
            while(!queue.isEmpty()){
                TreeNode t = queue.remove();
                if(t!=null){
                    lst.add(t.val);
                if(t.left != null){
                    queue.add(t.left);
                    end = t.left;
                }
                if(t.right != null){
                    queue.add(t.right);
                    end = t.right;
                }
                if(t == last ){
                    list.add(lst);
                    last =end;
                    lst = new ArrayList<>();
                }
                }   
            } 
              return list;
        }
}