二叉树层级遍历

LintCode 二叉树层级遍历

解题思路：队列（先进先出）

将每层的节点插入到队列中， 然后遍历队列，再将下一层级的节点插入到队列中， 直到最后

如图中二叉树

image

先将根节点放入队列中如下图

image

然后遍历队列，循环取出队头元素，再将队元元素的左右节点放入到队列中，如下图

image

如此循环直到二叉树最深层级

代码如下：

public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        
        List<List<Integer>> tree = new ArrayList<List<Integer>>();
        if(root == null)
            return tree;
        queue.offer(root);
        while(!queue.isEmpty()){
            ArrayList<Integer> list = new ArrayList<Integer>();
            int size = queue.size();
            for(int i=0;i<size;i++){
                TreeNode head = queue.poll();
                list.add(head.val);
                if(head.left!=null){
                    queue.offer(head.left);
                }
                if(head.right!=null){
                    queue.offer(head.right);
                }
            }
            tree.add(list);
        }
        return tree;
    }