先簡單回顧一下，今天預計分析的題目：94. Binary Tree Inorder Traversal

題目敘述：https://leetcode.com/problems/binary-tree-inorder-traversal/

題目敘述：

• 題目會給一個二元樹結構的資料
  

測資的 Input/Output

• 會給一個指向 root 的資料
• 回傳中序排列
  

二元樹主要有四種遍歷/走訪(traversal) binary tree 的方法，分別為：

• 前序遍歷 (Preorder Traversal)
• 中序遍歷 (Inorder Traversal)
• 後序遍歷 (Postorder Traversal)
• 層序遍歷 (Level-order Traversal)

參考資料：https://ithelp.ithome.com.tw/articles/10205571

這邊針對中序進行簡單的介紹：

• 中序(inorder) 是一種遍歷/走訪(traversal) binary tree 的方法，對於任意節點，先走左側的 sub-tree，再走當前節點，最後走右側 sub-tree。

• 以此圖為例， inorder traversal 便會是 2→ +→ 3→ x→ 7
  

  • 從 root 開始，先走左側子樹，再走 x ，再走 7
    

  • 左側子樹的走法也是同樣道理，先走 2 ，再走 + ，最後走 3
    

  • 因此整個順序如下
    

實作方法

• 遞迴

  • 我們可以用 DFS 輕鬆實現中序走訪，首先開一個 list 存放答案

  ans = []
  

  • 使用遞迴方式實作，首先確定終止條件： 當節點為 None，則停止。

  if node == None:
      return None
  

  • 若節點存在，則先走訪左側子樹

  traverse(node.left)
  

  • 接著走訪當前節點。本題需要 return 一個 list ，其中依照 inorder 順序存放節點的值，因此當走訪一個節點時，只需要將 value 存入 list 即可。

  ans.append(node.val)
  

  • 最後走訪右側子樹

  traverse(node.right)
  

  • 完整 Code 如下

  class Solution:
      def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
          ans = []
          def traverse(node):
              if node == None:
                  return None
  
              traverse(node.left)
              ans.append(node.val)    
              traverse(node.right)
  
          traverse(root)
          return ans
  

• 迭代

  • 程式邏輯
    1. 使用迴圈，先走訪該點的左 child 走到底，經過的節點都儲存於 stack 中
    2. 經歷過步驟1，拿出 stack 中資料，此節點會是尚未走訪過的左 child，我們將此點的 value 儲存於 ans 中 ( 因為中序是先讀取 左child → parent → 右child )
    3. 接著看該點的 右 child，並重複 1~3 步驟，直到走訪完全部的 Binary Tree
  • python 實作

  class Solution:
      def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
          stack = []
          ans = []
  #       當 root 與 stack 都為空，代表走訪完整個二元樹
          while root or stack:
  #           不斷走訪左child，直到樹的最左下角，每次走訪都存入 stack 中
              while root:
                  stack.append(root)
                  root = root.left
  #           將儲存在 stack 的資料拿出來
              root = stack.pop()
  #           ans 儲存 root.val
              ans.append(root.val)
  #           換走訪 root 的 右 child 
              root = root.right
          return ans