0102. Binary Tree Level Order Traversal (Medium)

Question

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

1
2
3
4
5

[
  [3],
  [9,20],
  [15,7]
]

分析/解題

給定一個二元樹，回傳其節點値的層序遍歷結果。

我們在先前的文章中，
已經提到過層序走訪(level-order traversal)的概念了，
按照題目範例，這邊要將level分層開來。

對於遞迴 解來說，如果使用一般的DFS的話，
我們將不知道哪一個節點位在哪一個level上，
故我們將必須加入變數level ，
讓level的值來幫助我們辨別要加到List的哪個level區塊中。

所以對於遞迴解而言，在主函式 中：

1. 檢查根節點
2. 將root的值加入第0層的list 中，再將該list加到答案res 中
3. 呼叫幫助用的函式，將level遞増代入 (表下一層)

在幫助用函式 中：

1. 先檢查代入進來的節點，
   若遇到NIL則表示到此為止 ，進行回傳即可。
2. 檢查目前res的size 和level 的關係，
   若相等則表示要開一個新的list(因為level從0起算 )；
   否則，找到對應level的list，將該節點的值加入。
3. 分別檢查左節點和右節點進行遞迴 。

觀察這樣子的遍歷方式，讀者應該可以發現一點：
幫助用的函式本質上就是在做pre-order traversal。 之所以會達成我們想要的效果，是因為我們額外記錄了level這個資訊。

如果使用迭代法 來解呢？
我們可以建立一個Queue ，在每一層先行取得Queue的大小(長度) ，
每次迴圈只要剛好執行這個次數，
就可以不斷利用相同的Queue來堆出不同的層數 ，
再分頭將對應的左節點和右節點推入Queue中 。
(記得要先檢查，非NIL才需要推入)
最終所有節點都遍歷過一遍時，
剛好Queue裡面也不會留存任何節點。

依照上述說明，請參考對應的程式碼。

Java的部分，記得用來檢查的isEmpty() ，以及可以用LinkedList 來實作Queue 的部分。

Java

Python用deque (記得我們提到過的，list在移除左端的部分效率較差 )
另外，若幫助函式沒有要再被其他函式使用，
是可以考慮如底下34行以後這樣子寫成子函式的方式再呼叫的，
可以省去要加一堆self的狀況。
(但要記得：Python函式要先宣告才能呼叫 )

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N)/O(N)，因為要遍歷全部節點並記錄)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~