1 題目描述


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

2 解法

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

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

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

2.1 取subtree的範圍

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

  1. 那就是如果我們先取得preorder的第一個值，就可以知道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
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    # 1. 找到 inorder 的 root 位置以切出左右子樹
    root = TreeNode(preorder[0]) 
    root_index = inorder.index(root.val) 
    
    # 2. 找到 inorder 的左右子樹
    i_left = inorder[0:root_index]
    i_right = inorder[root_index+1:]

Step2: 根據左右子樹的長度，在preorder切割左右子樹
因為我們用inorder知道了左右子樹的，我們就可以在 preorder 裡面從 preorder[0+1:] (root的下一個node) 開始切割左右子樹

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

大概是這種感覺：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    # 1. 找到 inorder 的 root 位置以切出左右子樹
    root = TreeNode(preorder[0]) 
    root_index = inorder.index(root.val) 
    
    # 2. 找到 inorder 的左右子樹
    i_left = inorder[0:root_index]
    i_right = inorder[root_index+1:]

    # 3. 用 inorder 左右子樹的長度，找出 preorder 的左右子樹
    left_len = len(i_left)
    p_left = preorder[1:left_len+1]
    p_right = preorder[left_len+1:]

    # 4. 然後我們就可以利用 preorder 的左右子樹，找到左右子樹的 root
    root.left = self.buildTree(p_left, i_left)
    root.right = self.buildTree(p_right, i_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
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    # 最小問題：當左右子樹為空時，回傳None
    if not preorder or not inorder:
            return None

    # 1. 找到 inorder 的 root 位置以切出左右子樹
    root = TreeNode(preorder[0]) 
    root_index = inorder.index(root.val) 
    
    # 2. 找到 inorder 的左右子樹
    i_left = inorder[0:root_index]
    i_right = inorder[root_index+1:]

    # 3. 用 inorder 左右子樹的長度，找出 preorder 的左右子樹
    left_len = len(i_left)
    p_left = preorder[1:left_len+1]
    p_right = preorder[left_len+1:]

    # 4. 然後我們就可以利用 preorder 的左右子樹，找到左右子樹的 root
    root.left = self.buildTree(p_left, i_left)
    root.right = self.buildTree(p_right, i_right)

    return root

精簡

我們稍微整理一下，這個遞迴的過程

  1. left_len 其實可以用 root_index 來取代，因為左子樹的長度就是 root_index
  2. 最後 就可以精簡成這樣
1
2
3
4
5
6
7
8
9
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    if not preorder or not inorder:
        return None
    root = TreeNode(preorder[0]) 
    root_index = inorder.index(root.val) 
    root.left = self.buildTree(preorder[1:root_index+1], inorder[0:root_index])
    root.right = self.buildTree(preorder[root_index+1:], inorder[root_index+1:])
    return root

總結一下順序：

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

這題的大問題與小問題的關係是

  1. 大問題：建立一個二元樹
  2. 小問題：建立左右子樹
  3. 大小問題的關聯式：假設知道 root.left 與 root.right 最後要回傳 root
    1. 左子樹的範圍是 preorder[1:root_index+1] 與 inorder[0:root_index]，右子樹的範圍是 preorder[root_index+1:] 與 inorder[root_index+1:]
    2. 我們要回傳 root，並且把左右子樹填入
    3. root 一定是 preorder 的第一個 node，因此 root.left 跟 root.right 就是左右子樹中 preorder 的第一個 node

2.2 queue 的解法

這題解法也很酷，你可以從上圖看到，preorder 儘管被切割成 left 與 right，但是我們真正會使用到 preorder 的地方就是 root = TreeNode(preorder[0]) 我們只是想拿 preorder 的第一個值，如果我們每次取完root後，就 pop 掉，下一個數值就會是肯定是子樹的root。因此我們也不用大費周章的去切割preorder，只要每次取完root後，就 pop 掉，下一個數值就會是肯定也會是某個子樹的root。

1
2
3
4
5
6
7
8
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    if inorder:
        INDEX = inorder.index(preorder.pop(0))
        root = TreeNode(inorder[INDEX])
        root.left = self.buildTree(preorder, inorder[:INDEX]) # 直接傳 preorder 進去(root已經被pop掉了)
        root.right = self.buildTree(preorder, inorder[INDEX+1:]) # 直接傳 preorder 進去(root已經被pop掉了)
        return root
    return None

3 總結

這題花了一個小時，概念是想出來了，但是還是寫不太出來Recursive…，後來看了一下解答，慢慢體會想法被實踐的感覺…呵呵。希望Recursion會慢慢進步。