二叉樹的層序遍歷

題目描述：給你一個二叉樹，請你返回其按 層序遍歷 得到的節(jié)點值。 （即逐層地，從左到右訪問所有節(jié)點）。

示例說明請見LeetCode官網(wǎng)。

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解法一：利用隊列遍歷二叉樹

隊列的特點是先進先出，所以利用隊列來遍歷二叉樹實現(xiàn)層序遍歷，具體過程如下：

• 首先，如果root為空，直接返回空的List。

• 如果root不為空，聲明一個隊列nodes，將root節(jié)點加入到隊列中，聲明一個result，然后遍歷nodes中的節(jié)點，遍歷過程如下：

• 首先，用count記錄當前隊列中節(jié)點的數(shù)量，即為當前層節(jié)點的數(shù)量，vals記錄當前節(jié)點的值；

• 從nodes中按順序取出count個節(jié)點，并且將相應(yīng)的節(jié)點值放入vals中，同時如果當前節(jié)點的左右子節(jié)點不為空，按從左到右的順序放入nodes中。然后將vals加入到結(jié)果result中。

• 重復遍歷nodes中的節(jié)點，直到nodes為空。

• 最后返回result即為層序遍歷的結(jié)果。

【每日寄語】 虛心使人進步，驕傲使人落后。