二叉樹的中序周遊_從前序與中序周遊序列構造二叉樹 (遞歸)

題目描述

根據一棵樹的前序周遊與中序周遊構造二叉樹。

注意:

你可以假設樹中沒有重複的元素。

例如，給出

前序周遊 preorder = [3,9,20,15,7]

中序周遊 inorder = [9,3,15,20,7]

傳回如下的二叉樹：

3
   / 
  9  20
    /  
   15   7
           

要點回顧

：

1、二叉樹前序周遊的順序為：先通路根節點、接着周遊左子樹、最後周遊右子樹。

2、二叉樹中序周遊的順序為：先周遊左子樹、再通路根節點、最後周遊右子樹。

根據題意來看，這個用遞歸來解比較容易了解。

遞歸解題思路

1、對于任意一顆二叉樹而言，根節點總是前序周遊中的第一個節點。

2、中序周遊的形式總是根節點将左右子樹分開：左子樹在根節點左側，右子樹在根節點右側。

隻要我們在中序周遊中定位到根節點，那麼我們就可以分别知道左子樹和右子樹中的節點數目。

即前序周遊為：[ 根節點, [左子樹的前序周遊結果], [右子樹的前序周遊結果] ]

中序為：[ [左子樹的中序周遊結果], 根節點, [右子樹的中序周遊結果] ]

3、由于同一顆子樹的前序周遊和中序周遊的長度顯然是相同的，是以按照上述格式切分出左子樹的前序周遊和中序周遊結果，以及右子樹的前序周遊和中序周遊結果;

4、遞歸地對構造出左子樹和右子樹，再将這兩顆子樹接到根節點的左右位置。

實作細節

：

在構造二叉樹的過程之前，先對中序周遊容器進行一次掃描，構造一個哈希表，鍵表示一個元素（節點的值），值表示其在中序周遊中的出現位置，這樣構造二叉樹的過程中，我們隻需要O(1)的時間就可以定位到根節點。

遞歸代碼模闆

：

遞歸結束條件、處理目前層邏輯、下沉到下一層、清理目前層（非必須）。

具體代碼實作

：

class Solution {   
public:
    TreeNode* buildProc(vector<int>& pre, int left, int right) {
        if (left > right) return nullptr;	    //遞歸結束條件
        auto i = hashMap[pre[idx]];
        auto root = new TreeNode(pre[idx++]); 	    //執行目前層邏輯
        root->left = buildProc(pre, left, i - 1);   //建構左子樹
        root->right = buildProc(pre, i + 1, right); //建構右子樹
        return root;
    }
    TreeNode* buildTree(vector<int>& pre, vector<int>& in) {
        auto len = in.size();
        for (auto i = 0; i < len; ++i) hashMap[in[i]] = i; //對中序周遊容器進行掃描
        return buildProc(pre, 0, len - 1);
    }
private:
    unordered_map<int, int> hashMap;	//哈希表
    int idx = 0;
};
           

AC結果

：