其實常見的tree traversal(前序、中序、後序拜訪)，
背後的核心觀念都是相同的。Tree traversal其實就是探索整顆樹的搜索空間，也可以說是探索整顆樹，只是指定順序略有不同而已。
再次回顧，經典的DFS模板
def dfs( parameter ):
if stop condition:
# update final result if needed
return result
# general cases:
dfs( updated parameter )
return result
宏觀的結構
應用到樹的搜索，preorder/ inorder/ postorder traversal 就變成
請留意註解中，有特別標出preorder / inorder / postorder 所在的順序
def dfs( parameter ):
if stop condition:
# update final result if needed
return []
# general cases:
# preorder: add current node to path
dfs( left sub tree )
# inorder: add current node to path
dfs( right sub tree )
# postorder: add current node to path
return path
其實三者背後的架構是共通的，只有次序稍微調整一下而已
具象化成preorder traversal，就變成了這個樣子
Preorder traversal 的拜訪順序與抽象模型
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
traversal_path = []
def preorder( node ):
if node:
# DFS with preorder:
# current, current.left, current.right
traversal_path.append( node.val )
preorder( node.left )
preorder( node.right )
# -----------------------------------
preorder(root)
return traversal_path
如果再用functional programming 的方式改寫，就變成
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
preOrder = lambda node: ( [node.val] + preOrder(node.left) + preOrder(node.right) ) if node else []
return preOrder(root)
再具象化成inorder traversal，就變成了這個樣子
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
traversal_path = []
def inorder( node ):
if node:
# DFS with inorder:
# current.left, current, current.right
inorder( node.left )
traversal_path.append( node.val )
inorder( node.right )
# -----------------------------------
inorder(root)
return traversal_path
如果再用functional programming 的方式改寫，就變成
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
inOrder = lambda node: ( inOrder(node.left) + [node.val] + inOrder(node.right) ) if node else []
return inOrder(root)
同樣的手法，
再具象化成postorder traversal，就變成了這個樣子
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
traversal_path = []
def postorder( node ):
if node:
# DFS with postorder:
# current.left, current.right, current
postorder( node.left )
postorder( node.right )
traversal_path.append( node.val )
# -----------------------------------
postorder(root)
return traversal_path
如果再用functional programming 的方式改寫，就變成
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
postOrder = lambda node: ( postOrder(node.left) + postOrder(node.right) + [node.val] ) if node else []
return postOrder(root)
Reference
[1] https://leetcode.com/problems/binary-tree-preorder-traversal/
[2] https://leetcode.com/problems/binary-tree-inorder-traversal/
[3] https://leetcode.com/problems/binary-tree-postorder-traversal/