引言

這兩道題主要是考察二叉樹遍歷的掌握，即由前序和中序推出原二叉樹，由后序和中序推出原二叉樹，這里先來說一下推導過程；
前序和中序
知道前序遍歷和中序遍歷，如何推原二叉樹？（直接是結論，可以自行推導一下）
1，先看前序的第一個元素first，這個元素值就是根節點的元素值
2，從中序遍歷中找到該元素first，該元素左邊的所有元素就是二叉樹的左子樹上的節點，右邊的所有元素就是二叉樹右子樹的節點，即將中序遍歷結果分為了兩部分
3，單看中序遍歷左邊，左邊所有元素誰在先序遍歷前面誰就是左樹的根節點，右樹一樣（其實就類似一直重復前兩步，一個遞歸過程），依次類推；

后序和中序
1，先看后序的最后一個元素last，這個元素值就是根節點的元素值
2，從中序遍歷中找到該元素last，該元素左邊的所有元素就是二叉樹的左子樹上的節點，右邊的所有元素就是二叉樹右子樹的節點，即將中序遍歷結果分為了兩部分
3，重復前兩步直到結束

可以發現前序和后序不同就是前序是從前面開始找的，后序是從后面開始找的；

這就是知道遍歷順序來推原二叉樹的過程，如果看不懂，還是建議在數據結構二叉樹的遍歷章節仔細研究一下，多試幾個例子就會了；

有了這個基礎，下面來說這兩道題；

105從前序與中序遍歷序列構造二叉樹

給定一棵樹的前序遍歷 preorder 與中序遍歷 inorder。請構造二叉樹并返回其根節點。

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]

提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均無重復元素
inorder 均出現在 preorder
preorder 保證為二叉樹的前序遍歷序列
inorder 保證為二叉樹的中序遍歷序列

我們已經知道如何推出原二叉樹的方法，在這里用代碼實現可能有點困難，我們來一一解決；
1，肯定能想到需要用到遞歸，我們只需要找到前序遍歷的第一個節點，然后分別遞歸生成左子樹和右子樹就可以了；
2，這里主要說一點就是如何在中序遍歷中找到根節點？ 這就可以用一個哈希表來快速查找到根節點的位置并返回下標；
這里就直接上代碼，注釋在代碼里更清楚

/*** 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 { public:int posFirst;unordered_map<int, int> hash;//該函數功能就是通過前序與中序遍歷序列構造二叉樹TreeNode* helper(int posLeft, int posRight, vector<int>& preorder, vector<int>& inorder) {//當左右子樹為空時，遞歸結束if (posLeft > posRight) return NULL;//找到根節點的val值，并創建根節點int rootVal = preorder[posFirst];TreeNode* root = new TreeNode(rootVal);//找到根節點在中序遍歷中的下標int index = hash[rootVal];//前序遍歷的坐標向后繼續，為了之后找到左右子樹的根節點posFirst++;//創建左子樹和右子樹，必需先左后右，因為posFirst是先過左子樹根節點再過右子樹根節點root -> left = helper(posLeft, index - 1, preorder, inorder);root -> right = helper(index + 1, posRight, preorder, inorder);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {posFirst = 0;int idx = 0;//將中序遍歷結果存放到哈希表中，key值為val，value值為下標for (auto& val : inorder) {hash[val] = idx++;}return helper(posFirst, inorder.size() - 1, preorder, inorder);} };

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

根據一棵樹的中序遍歷與后序遍歷構造二叉樹。

注意:
你可以假設樹中沒有重復的元素。

例如，給出
中序遍歷 inorder = [9,3,15,20,7]
后序遍歷 postorder = [9,15,7,20,3]
返回如下的二叉樹：

這道題和上面幾乎一模一樣，唯一區分點就根節點要從后序的后面找起，還有要先建右子樹，再建左子樹
代碼如下：

/*** 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 { public:int posLast;unordered_map<int, int> hash;//該函數功能就是通過后序與中序遍歷構造二叉樹TreeNode* helper(int posLeft, int posRight, vector<int>& inorder, vector<int>& postorder) {//當左右子樹為空時，遞歸結束if (posLeft > posRight) return NULL;//找到根節點的val值，并創建根節點int rootVal = postorder[posLast];TreeNode* root = new TreeNode(rootVal);//找到根節點在中序遍歷中的下標int index = hash[rootVal];//后序遍歷的坐標向前繼續，為了之后找到左右子樹的根節點posLast--;//創建右子樹和左子樹，必需先右后左，因為posLast是先過右子樹根節點再過左子樹根節點root -> right = helper(index + 1, posRight, inorder, postorder);root -> left = helper(posLeft, index - 1, inorder, postorder);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {posLast = (int)postorder.size() - 1;int idx = 0;//將中序遍歷結果存放到哈希表中，key值為val，value值為下標for (auto& val : inorder) {hash[val] = idx++;}return helper(0, posLast, inorder, postorder);} };

總結

這兩道題是非常經典的二叉樹遍歷題目，思路比較簡單，但是代碼實現可能會有點困難，所以一定要熟悉二叉樹的三種基本遍歷，并能靈活使用哈希表來幫助過程實現；

總結

以上是生活随笔為你收集整理的105从前序与中序遍历序列构造二叉树 106 从中序与后序遍历序列构造二叉树 (递归 + 哈希）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。