從上到下按層打印二叉樹(shù)，同一層的節(jié)點(diǎn)按從左到右的順序打印，每一層打印到一行。

示例

給定二叉樹(shù): [3,9,20,null,null,15,7],

3

/ \

9 20

/ \

15 7

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

[

[3],

[9,20],

[15,7]

]

提示

• 節(jié)點(diǎn)總數(shù) <= 1000

方法：分層遍歷+BFS

• 特例處理：當(dāng)樹(shù)的根節(jié)點(diǎn)為空，則直接返回空列表

• 初始化：初始返回的結(jié)果列表，并把根節(jié)點(diǎn)放入到隊(duì)列中

• 循環(huán)遍歷：

• 根據(jù)每層的葉子節(jié)點(diǎn)個(gè)數(shù)遍歷，注意這有個(gè)細(xì)節(jié)就是“int i = queue.size()”，因?yàn)楣?jié)點(diǎn)出棧，節(jié)點(diǎn)的大小是可變的

• 節(jié)點(diǎn)出隊(duì)

• 添加到層集合中

• 左/子節(jié)點(diǎn)非空時(shí)，入隊(duì)，用于下層遍歷

• 本層遍歷結(jié)束后，把層集合放入到結(jié)果列表中

• 終止條件：返回結(jié)果列表

流程如下兩個(gè)圖所示。

代碼如下：

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)，葉子結(jié)點(diǎn)出隊(duì)和入隊(duì)一次。

• 空間復(fù)雜度：O(n)，葉子結(jié)點(diǎn)的數(shù)量。

END

好兄弟可以點(diǎn)贊并關(guān)注我的公眾號(hào)“javaAnswer”，全部都是干貨。

業(yè)精于勤荒于嬉，行成于思?xì)в陔S，贈(zèng)友人。