利用队列实现 二叉树层次遍历（java）

思路

• 利用队列保存树的每一层，每一层添加入队列后加入一个null

• 队列不为空时循环出队列，遇到null的时候说明 下一层已经都进入队列中，上一层已经都依次出队列

例子

        1
      /   \
    2     3
         /   \
       4      5

queue:     [ 1, null ] 

            --> [null ,2, 3]-->[2, 3, null] --->[ 3, null](2 没有左右子树)

            -->[ null, 4, 5 ] -->[4,5,null] -->[5,null]-->[null]-->break loop;

具体代码

package arithmetic.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author fxs
 * @Description //TODO
 * @Date 2019/12/24
 **/
public class LevelTraversal {
    private static int level;

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
    static LinkedList<TreeNode> list = new LinkedList<>();

    public static List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        /**
         *  init (level==0)
         */
        list.addLast(root);//use queue ,add null after level++
        list.addLast(null); //The first layer of tree‘s data is stored in the queue
        ArrayList<Integer> inner = new ArrayList<>();
        inner.add(root.val);
        ArrayList<List<Integer>> res = new ArrayList<>();
        res.add(inner);
        while (!list.isEmpty()) {
            TreeNode treeNode = list.removeFirst();
            if (treeNode != null) { //
                if (treeNode.left != null) {
                    list.addLast(treeNode.left);
                }
                if (treeNode.right != null) {
                    list.addLast(treeNode.right);
                }
            } else {
                if (list.isEmpty()) break; //意味着全部遍历完了
                list.addLast(null); //意味着  上一层所有节点的子节点已经都添加了，这层结束了 
                // Shallow copy can be problematic
                inner = new ArrayList<>();
                for (TreeNode node : list) {
                    if (node != null) {
                        int val = node.val;
                        inner.add(val);
                    }
                }
                res.add(inner);
                level++;
            }
        }
        return res;
    }
}