請實現(xiàn)一個函數(shù)按照之字形順序打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右到左的順序打印，第三行再按照從左到右的順序打印，其他行以此類推。

示例

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

3

/ \

9 20

/ \

15 7

返回其層次遍歷結果：

[

[3],

[20,9],

[15,7]

]

提示

節(jié)點總數(shù) <= 1000

方法：雙端隊列+BFS

算法流程：

• 特例處理：當樹的根節(jié)點為空，則直接返回空列表。

• 初始化：初始結果集合、初始隊列并加入根節(jié)點

• 循環(huán)遍歷，為空時（即無葉子結點）跳出：

• 創(chuàng)建一個鏈表，用于存儲每一層的葉子節(jié)點；

• 遍歷每一層葉子節(jié)點，從隊列彈出元素；

• 根據(jù)結果集合的大小來判斷當前樹的層數(shù)，如果是偶數(shù)，加在鏈表尾部；否則加到鏈表頭部；

• 判斷左/右子節(jié)點非空，加入到隊列中，進行下一次遍歷；

• 返回結果集合；

圖解說明：

方法如下：

細節(jié)處理

• 細節(jié)1：基于 雙端隊列的特點，偶數(shù)行"按照從左到右的順序打印"，奇數(shù)行"按照從右到左的順序打印"

• 細節(jié)2：i = queue.size()，避免size的大小改變

• 細節(jié)3：根據(jù)結果集合的大小來判斷當前樹的層數(shù)

復雜度分析

• 時間復雜度：O(n)，每個節(jié)點入隊出隊各一次。

• 空間復雜度：O(n)，二叉樹的節(jié)點的個數(shù)。

END

好兄弟可以點贊并關注我的公眾號“javaAnswer”，全部都是干貨。

寶劍鋒從磨礪出，梅花香自苦寒來，贈友人。