目錄
- 1 前言
- 2 分類
- 3 遞歸周遊
- 4 非遞歸周遊
- 傳統層次周遊列印形式
- LeetCode 中題目列印方式
1 前言
大家好，「樹」的刷題已經有一段時間了。
一來二去時間上有所拖延。之前總結過「樹」的基礎周遊，這一篇來具體題目看看，對于基礎周遊能遇到哪些問題。
下圖是咱們之前規定的「基礎周遊」的一些題目。
圍繞，前中後序周遊對于N叉樹的适用性，已經層序周遊不同的列印方式，有哪些注意點。
題目如下：
102.二叉樹的層序周遊
https://leetcode-cn.com/problems/binary-tree-level-order-traversal
589.N 叉樹的前序周遊
https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal
107.二叉樹的層序周遊 II
https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii
145.二叉樹的後序周遊
https://leetcode-cn.com/problems/binary-tree-postorder-traversal
94.二叉樹的中序周遊
https://leetcode-cn.com/problems/binary-tree-inorder-traversal
429.N 叉樹的層序周遊
https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal
144.二叉樹的前序周遊
https://leetcode-cn.com/problems/binary-tree-preorder-traversal
590.N 叉樹的後序周遊
https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal
以上，在 github 記錄：https://github.com/xiaozhutec/share_leetcode
2 分類
前面我們說過一些基礎的「樹」的周遊，直達連結：https://mp.weixin.qq.com/s/nTB41DvE7bfrT7_rW_gfXw
有了之前的基礎，很直覺的，可以将上述周遊的題目分為兩類兩方面
兩類：
第一類，分别是前序周遊、中序周遊和後續周遊
第二類，層次周遊
兩方面：
第一方面，遞歸實作，适用于前序周遊、中序周遊和後續周遊
第二方面，非遞歸實作适用于前序周遊、中序周遊、後續周遊以及層次周遊
3 遞歸周遊
在之前 https://mp.weixin.qq.com/s/nTB41DvE7bfrT7_rW_gfXw 的一篇文章中已經詳細說過了遞歸的方式，大家可重新翻開看看。
然後該篇文章由于涉及到 N 叉樹的周遊方式，是以，咱們對二叉樹和N叉樹進行對比代碼設計，由于其相似性，很容易就破解這幾個題目
首先，定義「樹」結點類，二叉樹和 N叉樹的結點定義不同點
# 二叉樹
class TreeNode(object):
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
# N叉樹
class Node(object):
def __init__(self, val=None, children=[]):
self.val = val
self.children = children
看起來差別是二叉樹的左右孩子和 N叉樹的孩子們結點的差別，其實本質是一樣的，同理二叉樹的左右孩子也能寫成children清單的形式。
即：
# 二叉樹
class TreeNode(object):
def __init__(self, val, children=[]):
self.val = val
self.children = children
而這裡二叉樹的 children 隻有兩個孩子，即左孩子 left 和右孩子 right。
描述完上述的孩子結點的定義，下面再看看遞歸的周遊方式。
# 二叉樹
res = []
def pre_order(root):
if not root:
return
res.append(root.val)
pre_order(root.left)
pre_order(root.right)
# N叉樹
res = []
def pre_order(root):
if not root:
return
res.append(root.val)
for node in root.children:
pre_order(node)
看出差別了嗎？差別就在
res.append(root.val)
之後的代碼。
二叉樹的寫法是先遞歸左孩子，再遞歸右孩子。
N叉樹的寫法是，利用
for
循環，依次遞歸孩子結點。
是以，差別就是遞歸的寫法，二叉樹寫兩次遞歸，N叉樹寫N次遞歸
都是一樣的邏輯，是不是很簡單。類似于先序周遊，其中中序周遊和後續周遊，都是同樣的邏輯去處理（N叉樹，N可代表從2到n）
github 檢視詳細代碼：https://github.com/xiaozhutec/share_leetcode
4 非遞歸周遊
非遞歸周遊先序、中序和後續周遊的詳細邏輯在也這裡已經寫了，可以傳回頭看看 https://mp.weixin.qq.com/s/nTB41DvE7bfrT7_rW_gfXw，用長圖的形式以及講的非常明白了。
層次周遊在「樹-自頂向下」的類别中運用的比較多，相比較于遞歸解法，利用層次周遊更加容易了解，而且代碼架構比較單一，具體的介紹和案例會在下一篇《講透樹 | 自頂向下類别題目專題》中進行介紹。
本文的非遞歸周遊主要針對的是層次周遊。那為什麼之前講的比較明白了，這裡又會說呢？
是這樣，之前講解的層次周遊，咱們列印出來的形式和 LeetCode 題目中列印出來的形式是有些差別的。而且僅僅因為列印的差別，會引出不一樣的一個思路，後面很多情況都會遇到這樣的思維方式。
如下：
# 經典層次周遊列印形式
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
# LeetCode 中列印的形式
[['A'], ['B', 'C', 'D'], ['E', 'F', 'G', 'H', 'I']]
是的，LeetCode 中列印的形式是要求将每一層的結點元素單獨放到一個 list 中，最後再放置到一個大的 list 中。
傳統層次周遊列印形式
先來簡單回顧一下，傳統的列印方式。
跟着上述圖中的描述，動手畫一下就會明白特别的簡單。
一句話總結就是：
循環判斷隊列 queue 中是否有元素，如果有，通路該元素并且判斷該結點元素是否有孩子結點，如果有，孩子結點依次入隊 queue，否則，繼續循環執行。
看代碼：
while queue:
node = queue.pop()
res.append(node.val)
if node.left:
queue.appendleft(node.left)
if node.right:
queue.appendleft(node.right)
就是不斷判斷隊列中隊首是夠有元素，如果有元素，通路該結點元素，并且判斷該結點是否有孩子結點，如果有，則依次入隊。繼續循環判斷。
其實N叉樹來說的話，也是一樣的邏輯，隻不過是把二叉樹中的兩個孩子，換為N個孩子，進行入隊操作。
while queue:
node = queue.pop()
res.append(node.val)
for child_node in node.children:
queue.appendleft(child_node)
一樣的道理！是不是比較簡單。
LeetCode 中題目列印方式
也是用一幅圖來描述，相較于經典的層次周遊，每層單獨存放會稍微複雜一些，需要變換一點點思路。
核心一句話
queue 中存放的是目前層的結點集，level_queue 存放的下一層的結點集合。
每次循環周遊目前層queue中結點的同時，将該層結點集寫進一個臨時list，将下一層的結點入隊到 level_queue 中。之後将 level_queue 指派給 queue，循環執行，直到 queue 為空。
最後，将每層臨時 list 寫到一個大的 list 中
「點選下圖檢視高清原圖」????
上圖是以二叉樹進行舉例子，其實和 N叉樹的邏輯幾乎是一緻的，咱們先來看二叉樹的相關核心代碼：
def levelOrder(self, root):
res = []
if not root:
return res
queue = [root]
while queue:
level_queue = [] # 臨時記錄每一層結點
level_res = [] # 臨時記錄每一行的結點值
for node in queue: # 循環周遊每一層所有的結點
level_res.append(node.val)
if node.left:
level_queue.append(node.left)
if node.right:
level_queue.append(node.right)
queue = level_queue
res.append(level_res)
return res
類似的思路，來看看 N叉樹的層次周遊代碼：
def levelOrder_leetcode(self, root):
res = []
queue = [root]
if not root:
return res
while queue:
level_queue = [] # 臨時儲存每一層結點元素便于下一次進行疊代
level_res = [] # 臨時儲存每一層結點值
for node in queue:
level_res.append(node.val)
if node.children:
for child_node in node.children:
level_queue.append(child_node)
queue = level_queue
res.append(level_res)
return res
到這裡，應該已經非常熟悉二叉樹和N叉樹的一些差別了，依舊是在
level_res.append(node.val)
之後的幾行代碼的差別。
本篇文章主要是想說明開篇說的一些關于 LeetCode 上基礎的「樹周遊」的核心解決思路。
代碼和本文的文檔都在 https://github.com/xiaozhutec/share_leetcode，需要的小夥伴可以自行下載下傳代碼運作跑起來！
github 内容剛剛開始更新，感興趣的可以一起來學習。私信我 “LeetCode刷題” 群裡一起刷題進步。
手裡有 star 的，有空可以幫我點點 star。謝過大家！