根据前序遍历和中序遍历树构造二叉树.

 注意事项

你可以假设树中不存在相同数值的节点

您在真实的面试中是否遇到过这个题？ 

Yes

样例

给出中序遍历：[1,2,3]和前序遍历：[2,1,3]. 返回如下的树:

2 / \1   3 思路：若前序遍历为空或者中序遍历为空则返回空；                         创建根节点，前序遍历第一个节点是个根节点，在中序遍历中找到根节点相应的位置，可以分别得到左子树和右子树的前序和中序遍历。重建左右子树；                       使用辅助空间，存放被分割开的前序和中序遍历的序列。

/** * 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
       
         &preorder, vector
        
          &inorder) {        // write your code here                if(preorder.size()==0||inorder.size()==0){            return NULL;        }                if(preorder.size()!=inorder.size()){            return NULL;        }                vector
         
           preorder_l,preorder_r,inorder_l,inorder_r;        int root_index=-1;        int len=inorder.size();                        TreeNode* root=new TreeNode(preorder[0]);                        //  在中序队列中找出根节点位置        for(int i=0;i
          
           left=buildTree(preorder_l, inorder_l);        root->right = buildTree(preorder_r, inorder_r);                return root;    }};