根據前序序列和中序序列重建二叉樹

1 基本思路：前序周遊的第一個節點為根節點，找到根節點在中序周遊中的位置i。然後分别找到前序周遊中左子樹對應的部分，前序周遊中右子樹對應的部分，中序周遊中左子樹對應的部分，中序周遊中右子樹對應的部分，分别用四個數組來存儲。然後分别對左子樹、右子樹遞歸調用，傳入的參數也對應發生改變。

2 代碼實作：

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
     TreeNode* reConstructBinaryTree(vector<int>pre,vector<int>in) {
     //考慮邊界情況：由于pre和in的size總是相同
     int inlen=in.size();
     if(inlen==0)
         return NULL;
     
     //先序周遊序列的首元素是根節點
     TreeNode * head=new TreeNode(pre[0]);
     //查找根節點在中序周遊序列中的位置，pos用來存儲這個位置
     int pos=find(in.begin(),in.end(),pre[0])-in.begin();  
     //用left_pre存儲前序序列中的左子樹，left_in存儲中序序列中的左子樹
     //用right_pre存儲前序序列中的右子樹，right_in存儲中序序列中的右子樹
     vector <int> left_pre,left_in,right_pre,right_in;
     for(int i=0;i<pos;i++)
     {
         left_in.push_back(in[i]);
         left_pre.push_back(pre[i+1]);
     }
     for(int i=pos+1;i<inlen;i++)
     {
         right_in.push_back(in[i]);
         right_pre.push_back(pre[i]);
     }
     //将左子樹的前序中序序列傳入，遞歸建構左子樹
     head->left=reConstructBinaryTree(left_pre,left_in);
     head->right=reConstructBinaryTree(right_pre,right_in);
         
     //每次遞歸調用傳回根節點
     return head;
    }
};
           

3 注意事項：

①需要考慮邊界情況，即當左子樹序列或者右子樹序列元素的個數為0的時候，傳回值為空

②使用find()-in.begin()擷取根元素在中序序列的位置，因為find()的傳回值和begin()是同種類型，是以可以做運算。

③前序序列和中序序列分别對應的左子樹和右子樹的範圍及更新是遞歸的前提

④每次遞歸調用都傳回目前樹的根節點。

4 文法收獲：

①可以對vector的begin()和end()取内容(*)獲得數組的首尾元素，注意end需要減1

②查找數組中是否有值為XX的元素并傳回其下标

int i=find(a.begin(),a.end(),val)-a.begin()

使用find時添加頭檔案algorithm

find傳回值是vector對應的疊代器類型,與begin()傳回值類型相同，是以可以做運算

③ vector類型的好處是既可以通過指針通路，也可以通過下标通路

④不管是連結清單的節點還是樹的節點，都可以在結構體内加一個構造函數，友善建立節點的時候直接初始化。

例如：

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

構造函數中使用參數清單初始化成員，注意參數清單的基本格式。

5 報錯記錄

編譯報錯：too few arguments to function call,expected 6,have 2

報錯原因：形參和實參個數不符 收獲：牛客網劍指offer的題目要嚴格按照它的定義來，因為是按照它的定義來測試用例的，如果修改，用例會因為參數傳遞不通過。