---

一、leetcode-105

从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

样例输入：preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

样例输出： [3,9,20,null,null,15,7]

---

二、题解

1.引库

 #include <iostream>#include <cstdio>#include <cstdlib>#include <queue>#include <stack>#include <algorithm>#include <string>#include <map>#include <set>#include <vector>using namespace std;

2.代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if(preorder.size()==0) return NULL;int pos=0,n=preorder.size();while(inorder[pos]!=preorder[0]) pos++;TreeNode *root=new TreeNode(preorder[0]);vector<int> preArr,inArr;for(int i=1;i<=pos;i++) preArr.push_back(preorder[i]);for(int i=0;i<pos;i++) inArr.push_back(inorder[i]);root->left=buildTree(preArr,inArr);preArr.clear(),inArr.clear();for(int i=pos+1;i<n;i++) preArr.push_back(preorder[i]);for(int i=pos+1;i<n;i++) inArr.push_back(inorder[i]);root->right=buildTree(preArr,inArr);return root;}
};