**一. 題目描述** Given preorder and inorder traversal of a tree, construct the binary tree.? Note: You may assume that duplicates do not exist in the tree. **二. 題目分析** 這道題考察了先序和中序遍歷，先序是先訪問根節點，然后訪問左子樹，最后訪問右子樹；中序遍歷是先遍歷左子樹，然后訪問根節點，最后訪問右子樹。 做法都是先根據先序遍歷的概念，找到先序遍歷的第一個值，即為根節點的值，然后根據根節點將中序遍歷的結果分成左子樹和右子樹，然后就可以遞歸的實現了。 按照上述做法，時間復雜度為`O(n^2)`，空間復雜度為`O(1)` **三. 示例代碼** ~~~ #include <iostream> #include <algorithm> #include <vector> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { private: TreeNode* buildTree(vector<int>::iterator PreBegin, vector<int>::iterator PreEnd, vector<int>::iterator InBegin, vector<int>::iterator InEnd) { if (PreBegin == PreEnd) { return NULL; } int HeadValue = *PreBegin; TreeNode *HeadNode = new TreeNode(HeadValue); vector<int>::iterator LeftEnd = find(InBegin, InEnd, HeadValue); if (LeftEnd != InEnd) { HeadNode->left = buildTree(PreBegin + 1, PreBegin + (LeftEnd - InBegin) + 1, InBegin, LeftEnd); } HeadNode->right = buildTree(PreBegin + (LeftEnd - InBegin) + 1, PreEnd, LeftEnd + 1, InEnd); return HeadNode; } public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if (preorder.empty()) { return NULL; } return buildTree(preorder.begin(), preorder.end(), inorder.begin(), inorder.end()); } }; ~~~ **四. 小結** 該題考察了基礎概念，并不涉及過多的算法問題。