二元樹的拜訪 結合 DFS深度優先模板

其實常見的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/