題目

解題概念

  • 此題簡單來說，就是透過 Preorder 與 Inorder Traversal，去建構一 Binary Tree
    • 在 Binary Tree Traversal 中，只要是 Inorder + Preorder / Postorder 組合，一定可建構出一顆唯一的 Binary Tree
      • 原理 :
        • Preorder Traversal : 可以找出 Root
        • Inorder Traversal : 可以確認該 Root 左右子樹的元素
      • 詳細解釋 : 可參考此網頁
      • 補充 : 若是 Preorder + Postorder Traversal，則無法建構出唯一的 Binary Tree
    • 對 Binary Tree 的各種 Travesal 不熟的朋友可以參考此網頁
  • 此次解題，一樣是用遞迴的方式去解，而遞迴的終止條件如下 :
    • 當 Inorder 或 Preorder 陣列長度為 0 : 代表此樹為空，故直接回傳 Null 即可

實際寫Code

  • 目標函式 : buildTree(preorder, inorder)
    • 節點格式 : 
      1
      2
      3
      4
      5
      class TreeNode(object):
          def __init__(self, val=0, left=None, right=None):
              self.val = val
              self.left = left
              self.right = right
    • Input : preorder: List[int]、inorder: List[int]
    • Output : TreeNode
  • 前置作業 : 
    1
    2
    3
    4
    5
    6
    # 遞迴函數
    # def Recursion(pre_list, in_list): 
        # ...

    result = Recursion(preorder, inorder)
    return result
  • 遞迴函數 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    # pre_list : 此回合的前序元素陣列
    # in_list : 此回合的中序元素陣列
    def Recursion(pre_list, in_list):
        
        this_round = TreeNode() # 此回合的 Root 節點
            
        # 切割陣列
        root = pre_list[0] # pre_list的第一個元素，即為此回合的樹根
        root_index = in_list.index(root) # 取出樹根的索引值
            
        # 先依 Root 位置，切割 Inorder 陣列
        # 將 in_list 中位於 root 左邊的元素，放入 left_in_list，當作左子樹的 Inorder Traversal
        left_in_list = in_list[:root_index]
        # 將 in_list 中位於 root 右邊的元素，放入 right_in_list，當作右子樹的 Inorder Traversal
        right_in_list = in_list[root_index+1:] 
            
        # 再依左右子樹Inorder的元素數量，切割 Preorder 陣列
        # 補充 : 以下的 root_index 即為是左子樹 Inorder 陣列的數量
            # EX : 假設 index 為 1 ，則代表左子樹只會有 1 個元素
        # 將pre_list[1 ~ 左子樹數量]，放入 left_pre_list，當作左子樹的 Preorder Traversal
        left_pre_list = pre_list[1:root_index + 1] 
        # 將pre_list[左子樹數量 + 1 ~ 陣列底]，放入 right_pre_list，當作右子樹的 Preorder Traversal
        right_pre_list = pre_list[root_index+1: len(pre_list)]
           
        # 最後建構 Binary Tree            
        this_round.val = root # 放入 Root 的值 
        
        # 設定終止條件
        if len(left_in_list) == 0 :
            this_round.left = None
        else : 
            # 跑左子樹的遞迴
            this_round.left = Recursion(left_pre_list, left_in_list)
        if len(right_in_list) == 0 :
            this_round.right = None
        else :
            # 跑右子樹的遞迴
            this_round.right = Recursion(right_pre_list, right_in_list)

    return this_round

參考資料

  1. 用 Preorder 與 Inorder traversal 畫出 binary tree
  2. Binary Tree: Traversal(尋訪)