題目敘述 145. Binary Tree Postorder Traversal
題目給定一個二元樹的根結點。
請輸出後序拜訪(Post-order traversal)的拜訪序列。後序拜訪的定義:
1.拜訪左子樹。
2.拜訪右子樹。
3.拜訪目前的節點。
示意圖
測試範例
Example 1:
Input: root = [1,null,2,3]
Output: [3,2,1]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [1]
Output: [1]
約束條件
Constraints:
- The number of the nodes in the tree is in the range
[0, 100].
節點總數目介於0~100之間。
請注意，題目有可能給一個空樹。
-100 <= Node.val <= 100
節點值都介於-100 ~ 100之間。
進階提問
Follow up: Recursive solution is trivial, could you do it iteratively?
遞迴的方式很簡單，請問你能使用迭代的方式完成後序拜訪嗎?
演算法 遞迴法 依據定義實現
其實不管是哪一層，哪一個節點，後序拜訪的規則都是相同的，
只要根據後序拜訪的定義，寫出遞迴function即可。
後序拜訪的定義:
1.拜訪左子樹。
2.拜訪右子樹。
3.拜訪目前的節點。
程式碼 遞迴法 依據定義實現
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
traversal_path = []
if not root:
# empty node or empty tree
return []
else:
# DFS with postorder
# left child, right child, current node
traversal_path.extend( self.postorderTraversal( root.left ) )
traversal_path.extend( self.postorderTraversal( root.right ) )
traversal_path.append( root.val )
return traversal_path
複雜度分析
時間複雜度: O(n)
每個節點拜訪一次，總共n個節點。
空間複雜度: O(n)
每個節點拜訪一次，總共n個節點。
當整棵樹向左歪斜或者向右歪斜時，具有最大樹高O(n)，也是最深的遞迴深度。
程式碼 遞迴法 + python generator
對python generator概念和yield與unpacking *語法熟悉的讀者，
也可使用generator生成器的概念，直接在遞迴時動態輸出拜訪結果。
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def postorder( node ):
## Base case on empty node or empty tree
if not node:
return
## General cases
yield from postorder(node.left)
yield from postorder(node.right)
yield node.val
# --------------------------------------
return [*postorder(root)]
複雜度分析
時間複雜度: O(n)
每個節點拜訪一次，總共n個節點。
空間複雜度: O(n)
每個節點拜訪一次，總共n個節點。
當整棵樹向左歪斜或者向右歪斜時，具有最大樹高O(n)，也是最深的遞迴深度。
程式碼 迭代法 搭配stack
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
traversal_path = []
stack_postorder = [ (root, "init") ]
while stack_postorder:
current, label = stack_postorder.pop()
if not current:
# empty node
continue
elif label != "c":
# DFS with postorder
# left child, right child, current node
# Stack is of Last In First Out,
# thus push in reverse of postorder
stack_postorder.append( (current, "c") )
stack_postorder.append( (current.right, "r") )
stack_postorder.append( (current.left, "l") )
elif label == "c":
traversal_path.append( current.val )
return traversal_path
複雜度分析
時間複雜度: O(n)
每個節點拜訪一次，總共n個節點。
空間複雜度: O(n)
每個節點拜訪一次，總共n個節點。
當整棵樹向左歪斜或者向右歪斜時，具有最大樹高O(n)，也是最長的stack長度。
結語
其實常見的tree traversal(前序、中序、後序拜訪)，
背後的核心觀念都是相同的。
Tree traversal其實就是探索整顆樹的搜索空間，也可以說是探索整顆樹，
只是指定順序略有不同而已。
有興趣的讀者可參考這篇文章，會用更宏觀的觀點看待樹的拜訪。
