寫在前面

本專欄專注于分析與講解【面試經典150】算法，兩到三天更新一篇文章，歡迎催更……

專欄內容以分析題目為主，并附帶一些對于本題涉及到的數據結構等內容進行回顧與總結，文章結構大致如下，部分內容會有增刪：

• Tag：介紹本題牽涉到的知識點、數據結構；
• 題目來源：貼上題目的鏈接，方便大家查找題目并完成練習；
• 題目解讀：復述題目（確保自己真的理解題目意思），并強調一些題目重點信息；
• 解題思路：介紹一些解題思路，每種解題思路包括思路講解、實現代碼以及復雜度分析；
• 知識回憶：針對今天介紹的題目中的重點內容、數據結構進行回顧總結。

---

Tag

【遞歸】【二叉樹】

---

題目來源

106. 從中序與后序遍歷序列構造二叉樹

---

題目解讀

給你一棵二叉樹的中序和后續遍歷得到的兩個數組，現在根據兩個數組來構造二叉樹。

---

解題思路

方法一：遞歸

前言

首先回憶一下二叉樹的中序和后續遍歷過程。

二叉樹的中序遍歷過程：

• 先遞歸遍歷左子樹；
• 接著遍歷根節點；
• 最后遞歸遍歷右子樹。

二叉樹的后續遍歷過程：

• 先遞歸遍歷左子樹；
• 接著遞歸遍歷右子樹；
• 最后遍歷根節點。

在「遞歸」遍歷子樹的過程中，我們也是將子樹看成是一棵全新的樹，按照相應的順序進行遍歷。

思路

根據后續遍歷的順序可知，后續遍歷數組的最后一個元素為根節點。

于是可以根據后續遍歷數組中的根節點定位到中序遍歷中的根節點，接著可以將前序遍歷數組分為左子樹、根、右子樹三部分，針對左子樹和右子樹這兩個部分可以利用遞歸來完成二叉樹的構造。

算法

我們需要查找后續遍歷中的元素在中序遍歷中的位置，為了高效查找，利用一個哈希表 idx_map 來記錄中序遍歷中元素的位置。

接著定義遞歸函數 helper(in_left, in_right) 表示在中序遍歷的當前范圍內（中序遍歷的 [in_left, in_right]）遞歸構造二叉樹，遞歸入口為 helper(0, n - 1)：

• 遞歸出口：如果 in_left > in_right，說明子樹為空，返回空節點；
• 選擇后續遍歷的最后一個節點作為根節點；
• 在哈希表 idx_map 中查詢根節點在中序遍歷中的 idx。從 in_left 到 idx - 1 數屬于左子樹，從 idx + 1 到 in_right 屬于右子樹；
• 根據后續遍歷邏輯，遞歸創建右子樹 helper(idx + 1, in_right) 和左子樹 helper(in_left, idx - 1)。
• 最后返回根節點 root。

注意：在遞歸創建子樹的時候，先創建右子樹，再創建左子樹。因為在后續遍歷中是先存儲左子樹的節點，再存儲右子樹的節點，最后存儲根節點，如果每次選擇「后續遍歷的最后一個節點」為根節點，則先被構造出來的應該為右子樹。

/*** Definition for a binary tree node.* 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 {
private:int root_idx;unordered_map<int, int> idx_map;
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {root_idx = postorder.size() - 1;// 建立哈希表int idx = 0;for (auto val : inorder) {idx_map[val] = idx++;}function<TreeNode*(int, int)> helper = [&](int in_left, int in_right) -> TreeNode* {if (in_left > in_right) {return nullptr;}// 選擇 后續遍歷數組的最后一個元素作為當前子樹的根節點int root_val = postorder[root_idx--];TreeNode* root = new TreeNode(root_val);// 根據 root_val 所在位置分為左右兩棵子樹int idx = idx_map[root_val];// 遞歸構建右子樹 root->right = helper(idx + 1, in_right);// 遞歸構建左子樹root->left = helper(in_left, idx - 1);return root;};return helper(0, inorder.size() - 1);}
};

復雜度分析

時間復雜度：$O(n)$，$n$ 為數中節點個數。

空間復雜度：$O(n)$。

---

寫在最后

如果您發現文章有任何錯誤或者對文章有任何疑問，歡迎私信博主或者在評論區指出 💬💬💬。

如果大家有更優的時間、空間復雜度的方法，歡迎評論區交流。

最后，感謝您的閱讀，如果有所收獲的話可以給我點一個 👍 哦。