前序遍历和中序遍历构造二叉树[lintcode]

/** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { /** *@param preorder : A list of integers that preorder traversal of a tree *@param inorder : A list of integers that inorder traversal of a tree *@return : Root of a tree */ public: TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) { // write your code here vector<int> pre_l,pre_r,in_l,in_r;//定义这四个变量来存储左右子树的前序和中序序列 TreeNode* root=NULL; int i=0; int index=0; if(!preorder.empty()||!inorder.empty())//如果序列中不为空，继续构建 { root=new TreeNode(preorder[0]); for(i=0;i<inorder.size();i++) { if(preorder[0]==inorder[i]) { index=i;//找出分割中序序列的分割点，左边为左子树的，右边为有子树的 break; } } for(i=0;i<index;i++)//重新找出前面部分前中序列 { pre_l.push_back(preorder[i+1]); in_l.push_back(inorder[i]); } for(i=index+1;i<inorder.size();i++)//找出后面部分的前中序列 { pre_r.push_back(preorder[i]); in_r.push_back(inorder[i]); } //依次构建分割的部分，缩小区间，直至构建完 root->left=buildTree(pre_l,in_l); root->right=buildTree(pre_r,in_r); } return root; } };