刷题之从前序遍历与中序遍历序列构造二叉树（leetcode)

从前序遍历与中序遍历序列构造二叉树

前序遍历：中左右
中序遍历：左中右
前序遍历的第一个数必定为根节点，再到中序遍历中找到该数，数的左边是左子树，右边是右子树，进行递归即可。

#include<vector>
using namespace std;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 {
private:TreeNode* build(vector<int>& preorder, vector<int>& inorder){if (preorder.size() == 0)return NULL;//找到根节点int rootvalue = preorder[0];TreeNode* root = new TreeNode(rootvalue);//叶子节点if (preorder.size() == 1)return root;//区分左右子树位置int index = 0;for (int i = 0;i < inorder.size();i++){if (inorder[i] == rootvalue){index = i;break;}}vector<int>left_in(inorder.begin(), inorder.begin() + index);vector<int>right_in(inorder.begin() + index + 1, inorder.end());vector<int>left_pre(preorder.begin() + 1, preorder.begin() + 1 + left_in.size());vector<int>right_pre(preorder.begin() + 1 + left_in.size(), preorder.end());root->left = build(left_pre, left_in);root->right = build(right_pre, right_in);return root;}
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {return build(preorder, inorder);}
};int main()
{vector<int> preorder = { 3,9,20,15,7 };vector<int> inorder = { 9,3,15,20,7 };Solution solution;TreeNode* root=solution.buildTree(preorder, inorder);
}