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

注意事项

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

样例

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

  2

 /   1  3

标签

二叉树

code

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