題目

題目鏈接
給定兩個整數數組，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 <= preorder.length <= 30
• 1 <= preorder[i] <= preorder.length
• preorder 中所有值都 不同
• postorder.length == preorder.length
• 1 <= postorder[i] <= postorder.length
• postorder 中所有值都 不同
• 保證 preorder 和 postorder 是同一棵二叉樹的前序遍歷和后序遍歷

思路

考慮到二叉樹的前序遍歷與后序遍歷的特性，我們知道前序遍歷的第一個元素 preorder[0] 與后序遍歷的最后一個元素 postorder[n-1] 都對應著二叉樹的根節點。獲取了根節點后，我們需要將根節點的左子樹和右子樹區分開來，這里有兩種情況需要考慮：

1. 若原二叉樹的根節點的左子樹不為空，則 preorder[1] 對應著左子樹的根節點；
2. 若原二叉樹的根節點的左子樹為空，則 preorder[1] 對應著右子樹的根節點。

對于上述兩種情況，我們無法直接區分出 preorder[1] 到底是哪一種情況。但對于第二種情況，我們可以將原二叉樹的右子樹移到左子樹，這樣得到的二叉樹的前序遍歷數組與后序遍歷數組與原二叉樹相同。因為二叉樹的節點值互不相同，所以我們可以在后序遍歷數組中找到一個位置 k，使得 postorder[k] = preorder[1]，這樣左子樹的節點數目為 k+1。基于此思路，我們可以對前序遍歷數組和后序遍歷數組進行分治處理，將前序遍歷數組劃分為根節點、左子樹節點和右子樹節點三個部分，后序遍歷數組也劃分為左子樹節點、右子樹節點和根節點三個部分。因此，問題被劃分為：

1. 根據左子樹節點的前序遍歷與后序遍歷數組構造二叉樹；
2. 根據右子樹節點的前序遍歷與后序遍歷數組構造二叉樹。

當節點數目為 1 時，對應構造的二叉樹只有一個節點。我們可以遞歸地對問題進行求解，從而得到構造的二叉樹。

代碼

/*** 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:TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {int n = preorder.size();unordered_map<int, int> postMap;for (int i = 0; i < n; i++) {postMap[postorder[i]] = i;}return dfs(preorder, postorder, postMap, 0, n - 1, 0, n - 1);}TreeNode* dfs(vector<int>& preorder, vector<int>& postorder, unordered_map<int, int>& postMap, int preLeft, int preRight, int postLeft, int postRight) {if (preLeft > preRight) {return nullptr;}int leftCount = 0;if (preLeft < preRight) {leftCount = postMap[preorder[preLeft + 1]] - postLeft + 1;}return new TreeNode(preorder[preLeft],dfs(preorder, postorder, postMap, preLeft + 1, preLeft + leftCount, postLeft, postLeft + leftCount - 1),dfs(preorder, postorder, postMap, preLeft + leftCount + 1, preRight, postLeft + leftCount, postRight - 1));}
};

結果