題目描述

輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。

解題思路

用前序的順序重建整個二叉樹，先判斷傳進來參數是否合法，創建根結點，然后找到第一個根結點位置，遍歷整個中序順序，找到與前序序列第一個數相等的數的下標。然后創建左右子樹，左右子樹里又有左子樹和右子樹。

完整代碼

/*** 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> vin) {//先判斷合不合法int presize = pre.size();int vinsize = vin.size();if(pre.empty() || vin.empty())return NULL;//因為要建樹，所以要創建根結點TreeNode* root = new TreeNode(pre[0]);//找到中序遍歷的結點int firstroot = -1;for(int i = 0; i< vinsize; ++i){if(pre[0] == vin[i]){firstroot = i;break;}}//如果沒找到則返回if(firstroot == -1)return NULL;//歸并加遞歸創建左子樹和右子樹vector<int>left_pre,right_pre,left_vin,right_vin;for(int i =0 ;i< firstroot;++i){//在根節點左邊都是左子樹//左子樹的前序left_pre.push_back(pre[i+1]);//左子樹的中序left_vin.push_back(vin[i]);}for(int i = firstroot+1;i<vinsize;++i){//在根節點右邊都是右子樹//右子樹的前序right_pre.push_back(pre[i]);//右子樹的中序right_vin.push_back(vin[i]);}//根左右的左root->left = reConstructBinaryTree(left_pre,left_vin);//根左右的右root->right = reConstructBinaryTree(right_pre,right_vin);return root;}
};