iT邦幫忙

2021 iThome 鐵人賽

DAY 19
1
自我挑戰組

【帶你輕鬆入門演算法-Leetcode】系列 第 19

【第十九天 - Binary Tree題目分析】

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

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

  • 題目敘述:

    • 題目會給一個二元樹結構的資料
      https://ithelp.ithome.com.tw/upload/images/20210919/20140592kzfgh6Z2TJ.png
  • 測資的 Input/Output

    • 會給一個指向 root 的資料
    • 回傳中序排列
      https://ithelp.ithome.com.tw/upload/images/20210919/20140592ZSYYLtJYsh.png
  • 二元樹主要有四種遍歷/走訪(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+3x7
      https://ithelp.ithome.com.tw/upload/images/20210919/2014059261eNO28mYP.png

      • 從 root 開始,先走左側子樹,再走 x ,再走 7
        https://ithelp.ithome.com.tw/upload/images/20210919/20140592MI0CqqJMPI.png

      • 左側子樹的走法也是同樣道理,先走 2 ,再走 + ,最後走 3
        https://ithelp.ithome.com.tw/upload/images/20210919/20140592L2KyaaNLBA.png

      • 因此整個順序如下
        https://ithelp.ithome.com.tw/upload/images/20210919/20140592xUU2DrunUf.png

  • 實作方法

    • 遞迴

      • 我們可以用 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
      

上一篇
【第十八天 - Binary Tree介紹】
下一篇
【第二十天 - Graph 介紹】
系列文
【帶你輕鬆入門演算法-Leetcode】30

尚未有邦友留言

立即登入留言