105. Construct Binary Tree from Preorder and Inorder Traversal.md

105. Construct Binary Tree from Preorder and Inorder Traversal

思路

根据中序和前序遍历建树。
由于先序遍历的第一个肯定是根，所以原二叉树的根节点可以知道，然后由于树中没有相同元素，所以我们可以在中序遍历中也定位出根节点的位置， 并以根节点的位置将中序遍历拆分为左右两个部分，分别对其递归调用原函数。其中在中序遍历中定位根节点可以用个for循环也可以通过hash（即unordered_map，更快）。

需要提一点的是，同时知道前序遍历（或后序遍历）和中序遍历就能够唯一确定一颗二叉树，而前序和后序则不能。

C++

class Solution {
private:
    TreeNode* helper(int num, vector<int>& preorder, int pre_start, 
                     vector<int>& inorder, int in_start, 
                     unordered_map<int, int>& mp){
        if(num == 0) return NULL;
        int val = preorder[pre_start];
        TreeNode *node = new TreeNode(val);
        int i = mp[val] - in_start;
        node -> left = helper(i, preorder, pre_start + 1, inorder, in_start, mp);
        node -> right = helper(num-i-1, preorder, pre_start+i+1, inorder, 
                               in_start+i+1, mp);
        return node;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        unordered_map<int, int>mp;
        // 用map记录某个节点在中序遍历数组中的索引
        for(int i = 0; i < inorder.size(); i++) mp[inorder[i]] = i;
        return helper(preorder.size(), preorder, 0, inorder, 0, mp);   
    }
};