題目：

給定兩個整數數組?preorder 和 inorder?，其中?preorder 是二叉樹的先序遍歷， inorder?是同一棵樹的中序遍歷，請構造二叉樹并返回其根節點。

提示:

• preorder?和?inorder?均 無重復 元素

解法一（遞歸）：

在「遞歸」地遍歷某個子樹的過程中，我們也是將這顆子樹看成一顆全新的樹。在中序遍歷中定位到根節點，就可以分別知道左子樹和右子樹中的節點數目。由于同一顆子樹的前序遍歷和中序遍歷的長度顯然是相同的，因此我們可以對應到前序遍歷的結果中。

在中序遍歷中對根節點進行定位時，一種簡單的方法是直接掃描整個中序遍歷的結果并找出根節點，但這樣做的時間復雜度較高。我們可以考慮使用哈希表來幫助我們快速地定位根節點。對于哈希表映射中的每個鍵值對，鍵表示一個元素（節點的值），值表示其在中序遍歷中的出現位置。在構造二叉樹的過程之前，我們可以對中序遍歷的列表進行一遍掃描，就可以構造這個哈希映射。在此后構造二叉樹的過程中，我們就只需要O(1)的時間對根節點進行定位了。如下為實現代碼：

class Solution {
private:unordered_map<int, int> index;public:TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right){if(preorder_left>preorder_right){return nullptr;}// 前序遍歷中的第一個節點就是根節點int preorder_root = preorder_left;// 在中序遍歷中定位根節點int inorder_root = index[preorder[preorder_root]];// 先把根節點建立起來TreeNode* root = new TreeNode(preorder[preorder_root]);// 得到左子樹中的節點數目int size_left_subtree = inorder_root - inorder_left;// 遞歸地構造左子樹，并連接到根節點// 先序遍歷中【從左邊界+1開始的size_left_subtree】個元素就對應了中序遍歷中【從左邊界開始到根節點定位-1】的元素root->left = myBuildTree(preorder, inorder, preorder_left+1, preorder_left + size_left_subtree, inorder_left, inorder_root-1);// 遞歸地構造右子樹，并連接到根節點root->right = myBuildTree(preorder,inorder,preorder_left+1+size_left_subtree, preorder_right, inorder_root+1,inorder_right);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int n = preorder.size();// 構造哈希映射，幫助我們快速定位根節點for (int i = 0; i < n; ++i) {index[inorder[i]] = i;}return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);}
};

?時間復雜度：O(n)，其中n是樹中的節點個數。空間復雜度：O(n)，除去返回的答案需要的O(n)空間之外，我們還需要使用O(n)的空間存儲哈希映射，以及O(h)（其中h是樹的高度）的空間表示遞歸時棧空間。這里h<n，所以總空間復雜度為O(n)。

解法二（迭代）：

?對于前序遍歷中的任意兩個連續節點u和v，根據前序遍歷的流程，我們可以直到u和v只有兩種可能的關系：

1、v是u的左兒子。這是因此在遍歷之后，下一個遍歷的節點就是u的左兒子，即v；

2、u沒有左兒子，并且v是u的某個祖先節點(或者u本身)的右兒子，如果u沒有左兒子，那么下一個遍歷的節點就是u的右兒子。如果u沒有右兒子，我們就會向上回溯，直到遇到第一個有右兒子(且u不在它的右兒子的子樹中)的節點ua，那么v就是ua的右兒子。

我們用一個棧stack來維護「當前節點的所有還沒有考慮過右兒子的祖先節點」，棧頂就是當前節點。也就是說，只有在棧中的節點才可能連接一個新的右兒子。同時，我們用一個指針index指向中序遍歷的某個位置，初始值為0。index對應的節點是「當前節點不斷往左走達到的最終節點」，這也是符合中序遍歷的，它的作用在下面的過程中會有所體現。

首先我們將根節點3入棧，再初始化index所指向的節點為4，隨后對于前序遍歷中的每個節點，我們依次判斷它是棧頂節點的左兒子，還是棧中某個節點的右兒子。

我們遍歷9。9一定是棧頂節點3的左兒子。我們使用反證法，假設9是3的右兒子，那么3沒有左兒子，index應該恰好指向3，但實際上為4，因此產生了矛盾。所以我們將9作為3的左兒子，并將9入棧。

??? stack = [3, 9]
??? index -> inorder[0] = 4

我們遍歷8，5和4。同理可得它們都是上一個節點（棧頂節點）的左兒子，所以它們會依次入棧。

??? stack = [3, 9, 8, 5, 4]
??? index -> inorder[0] = 4

我們遍歷10，這時情況就不一樣了。我們發現index恰好指向當前的棧頂節點4，也就是說4沒有左兒子，那么10必須為棧中某個節點的右兒子。那么如何找到這個節點呢？棧中的節點的順序和它們在前序遍歷中出現的順序是一致的，而且每一個節點的右兒子都還沒有被遍歷過，那么這些節點的順序和它們在中序遍歷中出現的順序一定是相反的。

這是因為棧中的任意兩個相鄰的節點，前者都是后者的某個祖先。并且我們知道，棧中的任意一個節點的右兒子還沒有被遍歷過，說明后者一定是前者左兒子的子樹中的節點，那么后者就先于前者出現在中序遍歷中。

??? 因此我們可以把index不斷向右移動，并與棧頂節點進行比較。如果index對應的元素恰好等于棧頂節點，那么說明我們在中序遍歷中找到了棧頂節點，所以將index增加1并彈出棧頂節點，直到index對應的元素不等于棧頂節點。按照這樣的過程，我們彈出的最后一個節點x就是10的雙親節點，這是因為10出現在了x與x在棧中的下一個節點的中序遍歷之間，因此10就是x的右兒子。

??? 回到我們的例子，我們會依次從棧頂彈出4，5和8，并且將index向右移動了三次。我們將10作為最后彈出的節點8的右兒子，并將10入棧。
??????? stack = [3, 9, 10]
??????? index -> inorder[3] = 10

??? 我們遍歷20。同理，index恰好指向當前棧頂節點10，那么我們會依次從棧頂彈出10，9和3，并且將index向右移動了三次。我們將20作為最后彈出的節點3的右兒子，并將20入棧。
??????? stack = [20]
??????? index -> inorder[6] = 15

??? 我們遍歷15，將15作為棧頂節點20的左兒子，并將15入棧。
??????? stack = [20, 15]
??????? index -> inorder[6] = 15

??? 我們遍歷7。index恰好指向當前棧頂節點15，那么我們會依次從棧頂彈出15和20，并且將index向右移動了兩次。我們將7作為最后彈出的節點20的右兒子，并將7入棧。
??????? stack = [7]
??????? index -> inorder[8] = 7

此時遍歷結束，我們就構造出了正確的二叉樹。我們歸納出上述例子中的算法流程：

??? 我們用一個棧和一個指針輔助進行二叉樹的構造。初始時棧中存放了根節點（前序遍歷的第一個節點），指針指向中序遍歷的第一個節點；

??? 我們依次枚舉前序遍歷中除了第一個節點以外的每個節點。如果index恰好指向棧頂節點，那么我們不斷地彈出棧頂節點并向右移動index，并將當前節點作為最后一個彈出的節點的右兒子；如果index和棧頂節點不同，我們將當前節點作為棧頂節點的左兒子；

??? 無論是哪一種情況，我們最后都將當前的節點入棧。

最后得到的二叉樹即為答案。如下為實現代碼：

class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if (!preorder.size()) {return nullptr;}TreeNode* root = new TreeNode(preorder[0]);stack<TreeNode*> stk;stk.push(root);int inorderIndex = 0;for (int i = 1; i < preorder.size(); ++i) {int preorderVal = preorder[i];TreeNode* node = stk.top();if (node->val != inorder[inorderIndex]) {node->left = new TreeNode(preorderVal);stk.push(node->left);}else {while (!stk.empty() && stk.top()->val == inorder[inorderIndex]) {node = stk.top();stk.pop();++inorderIndex;}node->right = new TreeNode(preorderVal);stk.push(node->right);}}return root;}
};

筆者小記：

1、掌握二叉樹前序遍歷和中序遍歷的過程；

2、掌握二叉樹構建時，通過遞歸和迭代的方式添加二叉樹新節點的代碼書寫思路。

3、通過遞歸方式添加二叉樹新節點時有兩種方式，第一種：通過TreeNode*& root，引用的方式，root=new TreeNode(value)，以及遞歸調用root->left和root->right傳入到void的遞歸嵌套函數中，并返回return。第二種：return返回值的形式，root->left=遞歸嵌套返回值，root->rigth=遞歸嵌套函數返回值，其中嵌套函數返回值類型為TreeNode。

4、前序遍歷和中序遍歷都可以通過棧來實現迭代方法，棧的作用是在遍歷過程中顯示地模擬遞歸調用的行為（顯示的遞歸棧）。