例如，給出前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]返回如下的二叉樹：3/ 9  20/  15   7

For example, givenpreorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:3/ 9  20/  15   7

class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if(preorder.empty()) return NULL;TreeNode* root=new TreeNode(preorder[0]);vector<int> preorder_left, inorder_left, preorder_right, inorder_right;int i;for(i=0;i<inorder.size();++i){if(inorder[i]==root->val) break;inorder_left.push_back(inorder[i]);}//中序遍歷根結點的左子樹存入inorder_leftfor(++i;i<inorder.size();++i){inorder_right.push_back(inorder[i]);}//中序遍歷根結點的右子樹存入inorder_rightfor(int j=1;j<preorder.size();++j){//根據中序遍歷左子樹的長度來確定前序遍歷左子樹存入preorder_leftif(j<=inorder_left.size()) preorder_left.push_back(preorder[j]);//前序遍歷剩下的為右子樹 存入前序遍歷右子樹序列preorder_rightelse preorder_right.push_back(preorder[j]);}root->left=buildTree(preorder_left,inorder_left);root->right=buildTree(preorder_right,inorder_right);return root;}
};