從前序遍歷與中序遍歷序列構造二叉樹

前序遍歷：中左右
中序遍歷：左中右
前序遍歷的第一個數必定為根節點，再到中序遍歷中找到該數，數的左邊是左子樹，右邊是右子樹，進行遞歸即可。

#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);
}