題目敘述 N-ary Tree Postorder Traversal
題目給定一個N-ary(每個節點最多N個子樹)的樹根。
請返回後序拜訪這棵樹的軌跡。推廣後的後序拜訪的定義:
1.從左到右依序拜訪所有子樹。
2.拜訪目前的節點。
示意圖
測試範例
Example 1:
Input: root = [1,null,3,2,4,null,5,6]
Output: [5,6,3,2,4,1]
Example 2:
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]
約束條件
Constraints:
- The number of nodes in the tree is in the range
[0, 10^4].
節點總數目介於0~一萬。
請注意，題目有可能給一個空樹。
0 <= Node.val <= 10^4
節點值都介於0 ~ 一萬之間。
- The height of the n-ary tree is less than or equal to
1000.
樹高 <= 1000
進階提問
Follow up: Recursive solution is trivial, could you do it iteratively?
遞迴的方式很簡單，請問你能使用迭代的方式完成後序拜訪嗎?
演算法 遞迴法 依據定義實現
其實不管是哪一層，哪一個節點，後序拜訪的規則都是相同的，
只要根據後序拜訪的定義，寫出遞迴function即可。
推廣後的後序拜訪的定義:
1.從左到右依序拜訪所有子樹。
2.拜訪目前的節點。
程式碼 遞迴法 依據定義實現
class Solution:
def postorder(self, root: 'Node') -> List[int]:
if not root:
# base case:
# empty node or empty tree
return []
else:
# general case:
path = []
# Traverse children with postorder:
for child in root.children:
path += self.postorder( child )
# Travese current node with postorder:
path.append( root.val )
return path
複雜度分析
時間複雜度: O(n)
每個節點拜訪一次，總共n個節點。
空間複雜度: O(n)
每個節點拜訪一次，總共n個節點。
當整棵樹向左歪斜或者向右歪斜時，具有最大樹高O(n)，也是最深的遞迴深度。
程式碼 迭代法 搭配stack
class Solution:
def postorder(self, root: 'Node') -> List[int]:
# base case:
traversal_stack = [ (root, 'init') ]
path = []
# general case:
while traversal_stack:
current, label = traversal_stack.pop()
if current:
if label != 'cur':
# DFS with postorder
# left child, ...,right child, current node
# Stack is of Last In First Out,
# thus push in reverse of postorder
traversal_stack.append( (current, 'cur') )
for i in range( len(current.children)-1, -1, -1):
traversal_stack.append( (current.children[i],'child' ) )
else:
path.append( current.val)
return path
複雜度分析
時間複雜度: O(n)
每個節點拜訪一次，總共n個節點。
空間複雜度: O(n)
每個節點拜訪一次，總共n個節點。
當整棵樹向左歪斜或者向右歪斜時，具有最大樹高O(n)，也是最長的stack長度。
結語
其實常見的tree traversal(前序、中序、後序拜訪)，
背後的核心觀念都是相同的。
Tree traversal其實就是探索整顆樹的搜索空間，也可以說是探索整顆樹，
只是指定順序略有不同而已。
有興趣的讀者可參考這篇文章，會用更宏觀的觀點看待樹的拜訪。
🎄圖論應用: 二元樹的後序拜訪 Binary Tree Postorder Traversal_LC #145
