根据前序遍历和中序遍历还原二叉树

根据前序遍历和中序遍历还原二叉树:

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;

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

class Solution {
public:
    void createTree(vector<int>&pre,vector<int>&vin,int pre_left,int vin_left,int vin_right,TreeNode*& p){
        if(vin_left>vin_right)
            return;
        p = new TreeNode(pre[pre_left]);
        for(int i=vin_left;i<=vin_right;i++){
            if(vin[i]==pre[pre_left]){
            createTree(pre,vin,pre_left+1,vin_left,i-1,p->left);
            createTree(pre,vin,pre_left+i+1-vin_left,i+1,vin_right,p->right);
            break;
            }
        }

    }
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
         TreeNode* root;
         createTree(pre,vin,0,0,int(vin.size()-1),root);
         cout<<(root->val);
         return root;
    }
};
int main(){
    vector<int>pre={1,2,4,7,3,5,6,8};
    vector<int>vin={4,7,2,1,5,3,8,6};
    Solution ss;
    ss.reConstructBinaryTree(pre,vin);
}

根据前序遍历和中序遍历还原二叉树

原文：https://www.cnblogs.com/qiuhaifeng/p/11559928.html