二叉樹的層序遍歷，顧名思義，就是從左到右一層一層的去遍歷二叉樹。而每一層一層的遍歷都和左右節點有著很大的關系。也就是我們選用的數據結構不能一股腦的往一個方向鉆，而左右應該均衡考慮。這樣我們就選用隊列來實現。

我們先來看一個簡單的二叉樹的層序遍歷的例子：

給定二叉樹: [3,9,20,null,null,15,7],

3

   / \

  9  20

    /  \

   15   7

返回其層次遍歷結果：

[

  [3],

  [9,20],

  [15,7]

]

我們根據給出的信息總結一下例題：給定一棵二叉樹，把這棵二叉樹一層一層地訪問一遍，并且存儲在一個二維數組里面。

這里面的難點就是怎么做到每次取一層的元素。

我們考慮使用隊列來存儲每一層的元素。為什么使用隊列呢？因為對同一層的節點，先訪問，再把他們存儲到一個數組里，存儲的順序要和訪問的順序一致，而隊列的特點就是先進先出，和我們的要求一致，所以考慮使用隊列來實現本題。

算法如下：

1.首先，我們創建一個隊列，用來訪問節點（不一定是同一層）；創建一個列表，用來存儲同一層的節點；創建一個二維列表，用來存儲最終的答案。

2.然后，先對根節點做處理，把根節點加入隊列，用列表存儲，在二維列表里面加入剛才的列表，這樣，第一層節點就存儲好了。

3.到了第二層，我們再創建一個列表，用來存儲第二層的節點，并獲取一下隊列的長度，這里隊列的長度是多少，接下來就要進行幾次循環，每次循環是訪問并存儲當前節點的左子節點和右子節點。

4.每次循環要做的工作是：彈出隊列頭部的一個節點，將這個節點的左子節點和右子節點加入隊列，并且把左子節點和右子節點的值存進剛才的列表。

5.若干次循環完成后，隊列里面就都是下一層的節點，列表已經存好了這一層的節點。

6.把列表加入二維列表。

7.重復第3~6步，直到隊列為空。

對于隊列，現進先出。從根節點的節點push到隊列，那么隊列中先出來的順序是第二層的左右(假設有)。第二層每個執行的時候添加到隊列，那么添加的所有節點都在第二層后面。

同理，假設開始pop遍歷第n層的節點，每個節點會push左右兩個節點進去。但是隊列先進先出。它會放到隊尾(下一層)。直到第n層的最后一個pop出來，第n+1層的還在隊列中整齊排著。這就達到一個層序的效果。

實現代碼如下：

public List<List<Integer>> levelOrder (TreeNode root) {

    Queue<TreeNode> q = new LinkedList<>();

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

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

    if (root == null)

        return ans;

    ((LinkedList<TreeNode>) q).add(root);

    list.add(root.val);

    ans.add(list);

    while (q.size() > 0) {

        list = new ArrayList<Integer>();

        int s = q.size();

        for (int i = 0; i < s; i++) {

            TreeNode tn = q.remove();

            if (tn.left != null) ((LinkedList<TreeNode>) q).add(tn.left);

            if (tn.right != null) ((LinkedList<TreeNode>) q).add(tn.right);

            if (tn.left != null) list.add(tn.left.val);

            if (tn.right != null) list.add(tn.right.val);

        }

        if (list.size() > 0) {

            ans.add(list);

        }

    }

    return ans;

}

我們需要注意的是，在第12行，一定要用一個整形數來存隊列的大小，不能直接在循環條件里面使用i<q.size()，因為在循環體中，隊列大小是會變的，所以有必要用一個數來“固定”住這一層的隊列的長度。

二叉樹的層序遍歷只是二叉樹的遍歷方式中的一種，還有諸如前序遍歷、中序遍歷、后序遍歷等等遍歷方式。每一種遍歷方式都值得單獨拿出來好好說道，當然我們就不一一介紹了，感興趣的小伙伴可以在本站的數據結構和算法教程里一一學習，都有很詳細的講解。