二叉樹的層序遍歷，顧名思義，就是從左到右一層一層的去遍歷二叉樹。而每一層一層的遍歷都和左右節(jié)點(diǎn)有著很大的關(guān)系。也就是我們選用的數(shù)據(jù)結(jié)構(gòu)不能一股腦的往一個方向鉆，而左右應(yīng)該均衡考慮。這樣我們就選用隊列來實(shí)現(xiàn)。

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

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

3

   / \

  9  20

    /  \

   15   7

返回其層次遍歷結(jié)果：

[

  [3],

  [9,20],

  [15,7]

]

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

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

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

算法如下：

1.首先，我們創(chuàng)建一個隊列，用來訪問節(jié)點(diǎn)（不一定是同一層）；創(chuàng)建一個列表，用來存儲同一層的節(jié)點(diǎn)；創(chuàng)建一個二維列表，用來存儲最終的答案。

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

3.到了第二層，我們再創(chuàng)建一個列表，用來存儲第二層的節(jié)點(diǎn)，并獲取一下隊列的長度，這里隊列的長度是多少，接下來就要進(jìn)行幾次循環(huán)，每次循環(huán)是訪問并存儲當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。

4.每次循環(huán)要做的工作是：彈出隊列頭部的一個節(jié)點(diǎn)，將這個節(jié)點(diǎn)的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)加入隊列，并且把左子節(jié)點(diǎn)和右子節(jié)點(diǎn)的值存進(jìn)剛才的列表。

5.若干次循環(huán)完成后，隊列里面就都是下一層的節(jié)點(diǎn)，列表已經(jīng)存好了這一層的節(jié)點(diǎn)。

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

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

對于隊列，現(xiàn)進(jìn)先出。從根節(jié)點(diǎn)的節(jié)點(diǎn)push到隊列，那么隊列中先出來的順序是第二層的左右(假設(shè)有)。第二層每個執(zhí)行的時候添加到隊列，那么添加的所有節(jié)點(diǎn)都在第二層后面。

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

實(shí)現(xiàn)代碼如下：

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行，一定要用一個整形數(shù)來存隊列的大小，不能直接在循環(huán)條件里面使用i<q.size()，因為在循環(huán)體中，隊列大小是會變的，所以有必要用一個數(shù)來“固定”住這一層的隊列的長度。

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