leetcode No.102 二叉樹的層次遍歷

前兩天說過二叉樹的前序遍歷、中序遍歷、後續遍歷，把剩下的也都說了吧，二叉樹遍歷系列四，層次遍歷。

題目連結：

二叉樹的層次遍歷 - 力扣（LeetCode）

題目描述：

給定一個二叉樹，返回其按層次遍歷的節點值。 （即逐層地，從左到右訪問所有節點）。

例如：

給定二叉樹：

［3，9，20，null，null，15，7］

，

3

/ \

9 20

/ \

15 7

返回其層次遍歷結果：

［

［3］，

［9，20］，

［15，7］

］

解題思路：

不同於之前前中後序使用棧的方法，層序遍歷我們使用佇列。如果一個節點有左右孩子，就把它的左右孩子 push 到佇列中。

程式碼如下：

class

Solution

{

public

：

vector

<

vector

<

int

>>

levelOrder

（

TreeNode

*

root

）

{

if

（

！

root

）

return

{}；

vector

<

vector

<

int

>>

res

；

queue

<

TreeNode

*>

q

；

q

。

push

（

root

）；

while

（

！

q

。

empty

（））{

vector

<

int

>

v

；

int

size

=

q

。

size

（）；

for

（

int

i

=

0

；

i

<

size

；

++

i

）{

TreeNode

*

p

=

q

。

front

（）；

v

。

push_back

（

p

->

val

）；

if

（

p

->

left

）

q

。

push

（

p

->

left

）；

if

（

p

->

right

）

q

。

push

（

p

->

right

）；

q

。

pop

（）；

}

res

。

push_back

（

v

）；

}

return

res

；

}

}；

leetcode 裡還有倆題也是關於二叉樹的層次遍歷的，一是二叉樹的層次遍歷 II，是把二叉樹的元素按層次的順序自底向上輸出一遍，其實就是把本題最後的結果倒序一下就行了。二是二叉樹的鋸齒形層次遍歷，就是先從左到右，再從右到左，注意按照奇偶性，倒序每一行的元素就行，其他部分和本題完全一致，所以就不單獨寫一篇了。

如果有任何疑問，歡迎提出。如果有更好的解法，也歡迎告知。