106. 從中序與後序周遊序列構造二叉樹
題目來源：力扣（LeetCode）
https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal
題目
根據一棵樹的中序周遊與後序周遊構造二叉樹。
注意:
- 你可以假設樹中沒有重複的元素。
例如，給出
中序周遊 inorder = [9,3,15,20,7]
後序周遊 postorder = [9,15,7,20,3]
傳回如下的二叉樹：
3
/ \
9 20
/ \
15 7
解題思路
思路：遞歸
這道題中，主要考察的是如何利用 中序周遊 和 後序周遊 的特性去構造二叉樹。其中相似的題目有：
105. 從前序與中序周遊序列構造二叉樹
回到這道題，這裡先說下 中序周遊 和 後序周遊 的特性：
中序周遊 的輸出順序：左子樹 → 根節點 → 右子樹；
後序周遊 的輸出順序：左子樹 → 右子樹 → 根節點。
現在題目中給出 中序周遊 和 後序周遊 兩者的輸出序列，那麼我們就可以根據兩者的特性去構造二叉樹。具體的思路如下：
- 根據後序周遊的輸出順序，可以确定末尾元素就是根節點；
- 在中序周遊的輸出順序中，根節點左右的序列分别對應左子樹和右子樹的節點。那麼根據後序周遊确定的根節點，在中序周遊的序列中找到根節點對應的位置，進而确定左右子樹的節點；
- 當确定左右子樹節點時，此時要确定兩者在中序周遊和後續周遊序列中的邊界；
- 然後遞歸構造左右子樹；
- 遞歸傳回根節點 root。
這裡單純文字可能會有些拗口難懂，這裡畫出圖示來進行了解：
在後序周遊的序列中，找到根節點；
在中序周遊序列中定位根節點的位置，進而确定左右子樹的節點；
前面的思路中，還提及到邊界的問題。根據前面的圖示，我們可以直覺看出左右子樹的節點。但轉換成代碼時，我們需要明确一個範圍，在這裡用的是用索引位置去确定對應的邊界。
這裡說明下如何用索引位置去确定邊界：
後續的文字内容含義：
中序序列 表示中序周遊的輸出序列；
後序序列 表示後序周遊的輸出序列。
- 先定義變量：
-
in_left
-
in_right
-
in_root
-
post_left
-
post_right
-
post_root
-
- 當确定根節點之後，中序序列中，左右子樹的節點分别在根節點的左右兩側，由此确定兩者在中序序列的邊界：
- 左子樹邊界：
-
in_left
-
in_right
in_right = in_root - 1
-
- 右子樹邊界：
-
in_left
in_left = in_root + 1
-
in_right
-
- 左子樹邊界：
- 當中序序列中确定左右子樹的邊界後，這裡還需要确定在後序序列中的邊界。因為後序序列輸出順序為左右中，那麼隻要确定左子樹節點的個數，這裡就能确定左子樹的邊界，同樣也能進一步确定右子樹的邊界。
- 先求左子樹的節點個數，由中序序列可得：
size_of_left = in_root - in_left
- 确定後序序列左右子樹的邊界：
- 左子樹邊界：
-
post_left
-
post_right
size_of_left
post_right = post_left + size_of_left - 1
-
- 右子樹邊界：
-
post_left
post_left + size_of_left
-
post_right
post_root - 1
-
- 左子樹邊界：
這裡同樣用圖示來進一步了解（額外添加一個節點，隻為友善說明）：
在這裡額外提一下，由後序序列得到根節點，要在中序序列中定位其位置。Python list 有内置函數 index()，但是這裡查找時間為線性時間，可以考慮使用字典先存儲中序序列中元素以及對應的索引位置，這樣查找時間就會變為常數時間，也就是利用空間換時間。
以上就是具體的分析内容，具體的代碼如下：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
def build_tree(in_left, in_right, post_left, post_right):
if in_left > in_right:
return
# 後序序列末尾元素就是根節點
post_root = post_right
# 構造節點
root = TreeNode(postorder[post_root])
# 在中序序列定位根節點位置
in_root = inorder_map[root.val]
# size_of_right = in_right - in_root
# 擷取中序序列中左子樹的節點數
size_of_left = in_root - in_left
# root.left = build_tree(in_left, in_root-1, post_left, post_right-size_of_right-1)
# 遞歸建構左子樹
root.left = build_tree(in_left, in_root-1, post_left, post_left+size_of_left-1)
# root.right = build_tree(in_root+1, in_right, post_right-size_of_right, post_right-1)
# 遞歸建構右子樹
root.right = build_tree(in_root+1, in_right, post_left+size_of_left, post_root-1)
return root
size = len(inorder)
# 先用字典存儲中序序列，元素及其對應的索引位置
inorder_map = {}
for i in range(size):
inorder_map[inorder[i]] = i
return build_tree(0, size-1, 0, size-1)
歡迎關注
公衆号 【書所集錄】