題目描述

給定兩個整數數組 preorder 和 inorder ，其中 preorder 是二叉樹的先序遍歷， inorder 是同一棵樹的中序遍歷，請構造二叉樹并返回其根節點。

class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if(preorder.size()==0)return NULL;TreeNode* root = new TreeNode(preorder[0]);if(preorder.size()==1)return root;int index = 0;for (int i = 0; i < inorder.size(); ++i) {if(inorder[i]==preorder[0])index = i;}vector<int> leftIn(inorder.begin(), inorder.begin()+index);vector<int> rightIn(inorder.begin()+index+1, inorder.end());vector<int> leftPre(preorder.begin()+1,preorder.begin()+1+index);vector<int> rightPre(preorder.begin()+1+index,preorder.end());root->left = buildTree(leftPre,leftIn);root->right = buildTree(rightPre,rightIn);return root;}
};

小結：遞歸的思路也是非常清晰，C++的vector切割數組真的很方便，大概思路就是先用先序集合確定根結點，再找到在中序的位置，之后切割、遞歸。