題目資訊

題目編號: 889
題目連結: Construct Binary Tree from Preorder and Postorder Traversal
主題: Array, Hash Table, Divide and Conquer, Tree, Binary Tree

題目敘述

給定兩個整數數組，preorder 和 postorder，其中 preorder 是一個包含不同值的二元樹的前序遍歷，而 postorder 是相同二元樹的後序遍歷，重建並返回該二元樹。

如果存在多個答案，你可以返回其中任何一個。

範例 1：

範例圖片

輸入: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
輸出: [1,2,3,4,5,6,7]

範例 2：

輸入: preorder = [1], postorder = [1]
輸出: [1]

約束條件：

$1 \leq \text{preorder.length} \leq 30$
$1 \leq \text{preorder}[i] \leq \text{preorder.length}$
preorder 的所有值都是唯一的。
$\text{postorder.length} == \text{preorder.length}$
$1 \leq \text{postorder}[i] \leq \text{postorder.length}$
postorder 的所有值都是唯一的。
保證 preorder 和 postorder 是同一二元樹的前序遍歷和後序遍歷。

直覺

要從先序遍歷和後序遍歷重建二元樹，我們首先需要理解這兩種遍歷方法的特性。先序遍歷提供的是從上到下的根節點順序，而後序遍歷提供的是從下到上的根節點順序。基於這些特性，我們可以利用以下事實：先序遍歷的第一個元素是樹的根節點，後序遍歷的最後一個元素也是樹的根節點。

透過區分兩種遍歷中子樹的表示方式，我們可以遞迴地將遍歷拆分為表示左子樹和右子樹的片段。

解法

檢查基礎情況：首先檢查 preorder 列表是否為空。如果是空的，則沒有樹需要重建，因此返回 nullptr。
識別根節點：preorder 陣列的第一個元素始終是當前正在構建的子樹的根。因此，用該值創建一個 TreeNode。
單節點情況：如果 preorder 列表的大小為一，則表示我們正在處理單節點樹。此時，返回創建的根節點。
確定子樹邊界：preorder 列表中第二個元素是左子樹的根。在 postorder 列表中，左子樹元素出現在右子樹和子樹的根之前。為了找到左右子樹的邊界索引：
- 找到 postorder[postorder.size() - 2] 在 preorder 列表中的位置。這個索引告訴我們 preorder 列表中左子樹和右子樹的分界位置。
遞迴構建樹：
- 左子樹構建：使用表示左子樹的 preorder 元素和相關的 postorder 元素遞迴調用 constructFromPrePost 函數。
- 右子樹構建：類似地，使用它們的 preorder 和 postorder 片段對右子樹遞迴調用 constructFromPrePost 函數。
返回根節點：在構建完左子樹和右子樹後，將它們分別附加到根節點的左指針和右指針，然後返回根節點。

此方法有效利用了先序和後序序列的特性，將它們切分為適當的部分以便準確重建二元樹。

程式碼

C++

/**
 * 二元樹節點的定義。
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* constructFromPrePost(vector<int> preorder, vector<int> postorder) {
        // 如果前序列表為空，則沒有樹可構建
        if (preorder.empty()) {
            return nullptr;
        }
        
        // 前序的第一個元素是樹的根
        TreeNode* root = new TreeNode(preorder[0]);
        
        // 如果只有一個元素，那它就是一個單節點樹
        if (preorder.size() == 1) {
            return root;
        }

        // 找到分割前序列表為左、右子樹的索引
        int splitIndex = find(preorder.begin(), preorder.end(), postorder[postorder.size() - 2]) - preorder.begin();

        // 遞歸構建左子樹
        root->left = constructFromPrePost(
            vector<int>(preorder.begin() + 1, preorder.begin() + splitIndex), 
            vector<int>(postorder.begin(), postorder.begin() + splitIndex - 1)
        );

        // 遞歸構建右子樹
        root->right = constructFromPrePost(
            vector<int>(preorder.begin() + splitIndex, preorder.end()),
            vector<int>(postorder.begin() + splitIndex - 1, postorder.end() - 1)
        );

        return root;
    }
};

Python

class TreeNode:
    def __init__(self, x, left=None, right=None):
        self.val = x
        self.left = left
        self.right = right
        
class Solution:
    def constructFromPrePost(self, preorder, postorder):
        # 如果前序列表是空的，則沒有樹可以構造
        if not preorder:
            return None
        
        # 前序遍歷的第一個元素是樹的根節點
        root = TreeNode(preorder[0])
        
        # 如果只有一個元素，那麼這是一個單節點樹
        if len(preorder) == 1:
            return root

        # 找到分割前序列表為左子樹和右子樹的索引
        splitIndex = preorder.index(postorder[-2])

        # 遞歸構造左子樹
        root.left = self.constructFromPrePost(
            preorder[1:splitIndex], 
            postorder[:splitIndex - 1]
        )

        # 遞歸構造右子樹
        root.right = self.constructFromPrePost(
            preorder[splitIndex:],
            postorder[splitIndex - 1:-1]
        )

        return root

複雜度分析

時間複雜度: $O(n^2)$
時間複雜度為 $O(n^2)$，因為對於每次遞迴呼叫，程式使用 find 在 preorder 列表中定位下一個根節點的位置，這需要 $O(n)$ 的時間。該函數會對每個子樹進行遞迴呼叫，在最壞情況下，這導致 $n$ 次遞迴呼叫，每次呼叫需要 $O(n)$ 的操作來尋找分裂索引，從而導致總體複雜度為 $O(n^2)$。
空間複雜度: $O(n^2)$
空間複雜度為 $O(n^2)$，這是由於在每次遞迴呼叫中創建新的向量。在遞迴的每一層中，通過分割 preorder 和 postorder 陣列創建兩個新的向量，每個向量都會對空間使用量有貢獻。在最壞情況下，這些操作會導致二次的空間複雜度，因為你有深度 $O(n)$，且在每個深度，你可能會儲存 $O(n)$ 個元素。

CS Note
En

Leetcode 889. Construct Binary Tree from Preorder and Postorder Traversal

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析