1 題目描述


提供給你 postorder 與 inorder 的數列，請你建立一個二元樹。首先 讓我們先了解 postorder 與 inorder 的定義。
Inorder Traversal -> LEFT -> ROOT -> RIGHT
Postorder Traversal -> LEFT -> RIGHT -> ROOT

2 解法

這題跟 105 題很像，只是順序不同，這題是 postorder 與 inorder，105 題是 preorder 與 inorder。這題的解法也是利用遞迴的方式來建立二元樹。

你會發現，postorder 最後一筆會是 Root，前面會先遍歷left sub-tree整顆跑完，才會再遍歷right sub-tree。而 inorder 是先遍歷left sub-tree，再遍歷root，最後是right sub-tree。你會發現 preorder 跟 inorder 的優缺點如下：

  • postorder:
    • 好處：因為最後一個值是root，所以可以直接取得root的值
    • 缺點：無法知道左右子樹的範圍
  • inorder:
    • 好處：可以知道左右子樹的範圍
    • 缺點：無法知道root的值

因此我們要利用彼此雙方的好處，互補彼此的缺點。這時候我們就可以利用遞迴的方式來建立二元樹。

2.1 取subtree的範圍

Step1: 在postorder找到root + 在 inorder找到左右子樹長度

  1. 那就是如果我們先取得postorder的最後一個值，就可以知道root的值是什麼
  2. 然後再根據這個值去inorder中找到root的位置，這樣就可以知道左右子樹的範圍。
    1. 左子樹起點=0 ~ 左子樹 root_index (不包含) 簡單來說就是 inorder[0:root_index]
    2. 右子樹起點=root_index+1 ~ 右子樹結束點=len(inorder) (包含) 簡單來說就是 inorder[root_index+1:]

大概是這種感覺：

1
2
3
4
5
6
7
8
9
def buildTree(self, inorder: List[int], postorder: List[int], ) -> Optional[TreeNode]:
    # 1. 找到 inorder 的 root 位置以切出左右子樹
    root_val = postorder[-1]
    root = TreeNode(root_val)
    root_index = inorder.index(root_val)
    
    # 2. 找到 inorder 的左右子樹
    i_left = inorder[:root_index]
    i_right = inorder[root_index + 1:]

Step2: 根據左右子樹的長度，在postorder切割左右子樹
因為我們用inorder知道了左右子樹的，我們就可以在 postorder 裡面開始切割左右子樹

  1. 使用 i_left 的長度，在 [1:] 切割左子樹
  2. [0+1:] 這個區間是由 左子樹 + 右子樹 所組成
    1. 左子樹起點=0 ~ 左子樹結束點=1+left_len (不包含) 簡單來說就是 postorder[0:left_len+1]
    2. 右子樹起點=1+left_len ~ 右子樹結束點=-1 (包含) 簡單來說就是 postorder[left_len+1:-1]
  3. 從 postorder 得到的左右子樹，取最後一個值，又可以得到 root
  4. 把postorder從[:-1] 切成兩半左右子樹後，我們又可以開始遞迴，找到這兩個子樹的 root

大概是這種感覺：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def buildTree(self, inorder: List[int], postorder: List[int], ) -> Optional[TreeNode]:
    # Step 1: The last element in postorder is the root
    root_val = postorder[-1]
    root = TreeNode(root_val)
    
    # Step 2: Find the index of the root in inorder
    root_index = inorder.index(root_val)
    
    # Step 3: Split the inorder list into left and right subtrees
    i_left = inorder[:root_index]
    i_right = inorder[root_index + 1:]
    
    # Step 4: Split the postorder list into left and right subtrees
    p_left = postorder[:len(i_left)]
    p_right = postorder[len(i_left):-1]  # Exclude the last element which is the root
    
    # Step 5: Recursively build the left and right subtrees
    root.left = self.buildTree(i_left, p_left)
    root.right = self.buildTree(i_right, p_right)
    
    return root

Step3: 當左右子樹為空時，回傳None

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
def buildTree(self, inorder: List[int], postorder: List[int], ) -> Optional[TreeNode]:
    # Base case: if inorder or postorder is empty, return None
    if not inorder or not postorder:
        return None
        
    # Step 1: The last element in postorder is the root
    root_val = postorder[-1]
    root = TreeNode(root_val)
    
    # Step 2: Find the index of the root in inorder
    root_index = inorder.index(root_val)
    
    # Step 3: Split the inorder list into left and right subtrees
    i_left = inorder[:root_index]
    i_right = inorder[root_index + 1:]
    
    # Step 4: Split the postorder list into left and right subtrees
    p_left = postorder[:len(i_left)]
    p_right = postorder[len(i_left):-1]  # Exclude the last element which is the root
    
    # Step 5: Recursively build the left and right subtrees
    root.left = self.buildTree(i_left, p_left)
    root.right = self.buildTree(i_right, p_right)
    
    return root

精簡

稍微整理以下就可以變成這樣

1
2
3
4
5
6
7
8
def buildTree(self, inorder: List[int], postorder: List[int], ) -> Optional[TreeNode]:
    if not inorder or not postorder:
        return None
    root = TreeNode(postorder[-1])
    root_index = inorder.index(root.val)
    root.left = self.buildTree(inorder[:root_index], postorder[:root_index])
    root.right = self.buildTree(inorder[root_index + 1:], postorder[root_index:-1])
    return root

總結一下順序：

  1. inorder切出左右子樹: 在 inorder 用 root 切出左右子樹的範圍
  2. inorder找出左右子樹長度:拿 inorder 左右子樹的長度，在 postorder 切出左右子樹的範圍
  3. postorder 切出左右子樹，以找出root: postorder 的左右子樹一出來，就可以知道左右子樹的 root 是什麼（因為 postorder 的第一個值是root）
  4. 大小問題關係式: 然後把 root.left 與 root.right 填入

2.2 queue 的解法

跟 105 題一樣，可以使用queue去解這題，這樣就不用一直切割list，可以直接用index去取值，這樣會比較快。

1
2
3
4
5
6
7
8
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    if inorder:
        INDEX = inorder.index(postorder.pop(-1))
        root = TreeNode(inorder[INDEX])
        root.left = self.buildTree(inorder[0:INDEX], postorder[0:INDEX])
        root.right = self.buildTree(inorder[INDEX+1:], postorder[INDEX:])
        return root
    return None

3 總結

因為已經寫過了，所以大概30分鐘內就可以解決