Thursday, May 7, 2015

[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    TreeNode *buildTree(unordered_map<int, int> &map,
                        vector<int> &preorder,int ps, int pe, 
                        vector<int> &inorder, int is, int ie) 
    {
        if(ps>pe) return NULL;
        int i= map[preorder[ps]];
        TreeNode *node = new TreeNode(inorder[i]);
        node->left = buildTree(map,preorder, ps+1, ps+i-is, inorder, is, i-1);
        node->right = buildTree(map,preorder, ps+i-is+1, pe, inorder, i+1, ie);
        return node;
    }

    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        unordered_map<int, int> map;
        for(int i=0;i<inorder.size();i++)
        {
            map[inorder[i]] = i;
        }
        int len = preorder.size();
        return buildTree(map, preorder, 0, len-1, inorder, 0, len-1);
    }
};